Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 17 стр.

                                                                                   18

       printf("2, 3, 5");
       for (i = 6; i <= limit; i++) {
       // добавлена проверка делимости на 3 и 5. В оригинальной
       // версии алгоритма потребности в ней нет.
             if (is_prime[i]) && (i % 3 <> 0) && (i % 5 <> 0){
                printf(” % d ” , i); }
       }
       Обоснование алгоритма. Алгоритм полностью игнорирует любые
числа, которые делятся на три, пять и семь. Все числа, равные (по модулю
60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42,
44, 46, 48, 50, 52, 54, 56 или 58, делятся на два и заведомо не простые. Все
числа, равные (по модулю 60) 3, 9, 15, 21, 27, 33, 39, 45, 51 или 57, делятся на
три и тоже не являются простыми. Все числа, равные (по модулю 60) 5, 25,
35 или 55, делятся на пять и также не простые. Все эти остатки (по модулю
60) игнорируются.
       Все числа, равные (по модулю 60) 1, 13, 17, 29, 37, 41, 49 или 53, имеют
остаток от деления на 4 равный 1. Эти числа являются простыми тогда и
только тогда, когда количество решений уравнения 4x2 + y 2 = n нечётно и
само число не является квадратом (squarefree).
       Числа, равные (по модулю 60) 7, 19, 31 или 43, имеют остаток от
деления на 6 равный 1. Эти числа являются простыми тогда и только тогда,
когда количество решений уравнения 3x2 + y 2 = n нечётно и само число не
является квадратом.
       Числа, равные (по модулю 60) 11, 23, 47 или 59, имеют остаток от
деления на 12 равный 11. Эти числа являются простыми тогда и только тогда,
когда количество решений уравнения 3x2 − y 2 = n нечётно и само число не
является квадратом.
       Ни одно из рассматриваемых чисел не делится на 2, 3 или 5, значит
они не могут делиться и на их квадраты. Поэтому проверка того, что число
не является квадратом, не включает чисел 22, 32 и 52.