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

                                                                           31

      for (i = 6; i <= limit; i++) {
      // добавлена проверка делимости на 3 и 5. В оригинальной
      // версии алгоритма потребности в ней нет.
            if (is_prime[i]) && (i % 3 <> 0) && (i % 5 <> 0){
              printf(” % d ” , i); }
      }

      Обоснование алгоритма. Алгоритм основан на следующей теореме
Аткина:
      Теорема. Пусть n–натуральное число, свободное от квадратов (т.е. не
делящееся ни на какой квадрат простого числа) и удовлетворяющее условию
n ≡ 1 mod 4. Тогда, n – просто тогда и только тогда, когда

            #S = |{(x, y) : x > 0, y > 0, 4x2 + y 2 = n}| – нечетно

      Алгоритм полностью игнорирует любые числа, которые делятся на
три, пять и семь. Все числа, четные по модулю 60, делятся на два и заведомо
не простые. Все числа, равные (по модулю 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, значит
они не могут делиться и на их квадраты. Поэтому проверка того, что число