Нахождение первого числа, большего чем N, которое является относительным простым числом к ​​M

Question

В основном, название говорит обо всем.Числа не слишком велики (максимум для N составляет ~ 2/3 * max (длинный), а max M - max (long)), поэтому я думаю, что даже простого решения, которое у меня есть в данный момент, достаточно.M всегда больше, чем N.

То, что у меня сейчас есть:

• Самое простое, просто начните с N + 1, выполните простое евклидово GCD, и если оно вернет 1, мы закончим, если не увеличивать и попробуйте еще раз.

Я хотел бы знать, каков наихудший сценарий этого решения.Производительность не является большой проблемой, но все же я чувствую, что должен быть лучший способ.

Спасибо.

О худшем случае, я сделал небольшой тест:

Random r = new Random();
while (true)
            {
                long num = (long) r.Next();
                num *= r.Next();
                f((long)(num * 0.61), num);
            }

...

public static int max;

        public static int f(long N, long M)
        {
            int iter = 0;
            while (GCD(N++, M) != 1)
            {
                iter++;
            }

            if (iter > max)
            {
                max = iter;
                Console.WriteLine(max);
            }

            return 0;
        }

Он работает в течение ~ 30 минут, и наихудший случай пока составляет 29 итераций,Поэтому я считаю, что есть более точный ответ, чем O (N).

Answer 1

Я не знаю худшего сценария, но используя тот факт, что M <2 <sup>64 , я могу связать его выше на 292 итерации и ниже на 53 (сняв ограничение, что отношение N / M быть примерно исправленным).

Пусть p ₁ ,…, p _k - простые числа, большие или равные 5, на которые делится M. Пусть N '≥ N наименьшее целое число, такое, что N' = 1 mod 6 или N '= 5 mod 6. Для каждого i = 1,…, k простое число p _i делится не более чем на ceil ( 49 / p _i ) целых чисел N ', N' + 6, N '+ 12,…, N' + 288. Верхняя граница для ∑ _{i = 1,…, k} ceil (49 / p _i ) равен 101 _{i = 3,…, 16} ceil (49 / q _i ) = 48, где q - это простые числа в порядке, начинающемся с q ₁ = 2. (Это следует из того, что 10 _{i = 3,…, 17} ≥ 2 ⁶⁴ означает, что M является произведением не более 14 различных простых чисел, отличных от 2 и 3.) Мы заключаем, что по крайней мере одно из упомянутых целых чисел относительно простое по отношению к M.

Для нижней границы пусть M = 614889782588491410 (произведение первых пятнадцати простых чисел) и N = 1. После 1 первое целое число относительно простых пятнадцати простых чисел - шестнадцатое простое число, 53.

Я ожидаю, что обе границы могут быть улучшены без особой работы, хотя мне не ясно, с какой целью. Для верхней границы обработайте отдельно случай, когда 2 и 3 являются делителями M, так как тогда M может быть произведением не более тринадцати других простых чисел. Для нижней границы можно попытаться найти хороший M, запустив сито Эратосфена, чтобы вычислить для ряда целых чисел список простых чисел, разделяющих эти целые числа. Затем подметите окно через диапазон; если произведение отдельных простых чисел в окне слишком велико, продвиньте задний конец окна; в противном случае продвиньте передний конец.

Answer 2

Конечно, это не O (n), зная, что разрывы простых чисел - это log _e n, мы можем просто сказать, что ваш алгоритм имеет не более log _e n итераций (потому что после пропустив самое большее log _e n число, вы увидите новое простое число, которое является простым относительно вашего заданного числа n), для более подробной информации об этом разрыве, вы можете увидеть разрыв простых чисел .

Таким образом, для вашего ограниченного случая оно меньше, чем log _e n = log _e 2 ⁶⁴ <= 44 и будет меньше <code>44 итераций.