В.А. АВРУТИН

 

Московский государственный технический университет им. Н.Э. Баумана

 

АЛГОРИТМ ПОИСКА ПРОСТЫХ ЧИСЕЛ

В ЗАДАННОМ ИНТЕРВАЛЕ

 

Предлагается алгоритм поиска простых чисел в заданном интервале, основанный на матрице Сандарама.

 

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

Существуют, однако, и более элегантные методы построения списка простых чисел. Один из таких методов – «решето» Эратосфена – известен уже очень давно. Суть его сводится к следующему: выписываются все числа от 2 до n, затем берется первое число – 2 – и в списке помечаются все числа, делящиеся на 2 (каждое второе число из следующих за ним), затем берется следующее непомеченное число – 3 – и в списке помечаются все числа, делящиеся на него (т.е. каждое третье число из следующих за ним)… Эта операция продолжается до тех пор, пока не исчерпаются все непомеченные числа. Эти числа являются простыми, а список этих чисел – это список всех простых чисел от 2 до n.

Задача несколько усложняется, если требуется найти все простые числа от m до n, где m>2. В этом случае, применяя «решето» Эратосфена, приходится находить все простые числа от 2 до n, а потом отбрасывать те, которые меньше m (например, для нахождения всех простых чисел от 100000000 до 100000100 придется найти все простые числа от 2 до 100000100, а потом отбросить те, которые меньше 100000000).

Для решения подобного класса задач разработан алгоритм, сочетающий малые вычислительные затраты метода «решета» Эратосфена с возможностью работы в заданном интервале чисел. Этот алгоритм основан на таблице Сандарама (S.P.Sundaram, India).

 

4

7

10

13

16

19

7

12

17

22

27

32

10

17

24

31

38

45

Таблица 1

 

Таблица образована бесконечным числом бесконечных арифметических прогрессий, где каждый член первой прогрессии: 4, 7, 10, 13,… является первым членом новой арифметической прогрессии. Разности прогрессий – нечетные числа, начиная с 3: d1=3; d2=5; d3=7 и т.д. Если число N присутствует в этой таблице, тогда число 2N+1 составное, и наоборот, если N в таблице отсутствует, значит, число 2N+1 простое (в этом случае число N называют основой простого числа 2N+1). С помощью этой таблицы можно найти все простые числа за исключением числа 2. Очевидно, что таблица симметрична относительно главной диагонали. Не представляет сложности доказать, что S(x,y)=x+2xy+y – число в таблице, стоящее в столбце x строки y, а

D(n)=S(n,n)=2n(n+1) n-ое число главной диагонали этой таблицы.

Разработанный алгоритм использует указанные свойства таблицы  Сандарама и битовый массив, в нем отмечаются все числа N, которые не являются основами простых чисел из заданного диапазона. Для нахождения всех простых чисел от m до n анализируются все натуральные числа от m'=[(m-1)/2] до n'=[(n-1)/2] на предмет их вхождения в таблицу. Битовый массив B устроен таким образом, что бит B[0] хранит факт пометки числа m', B[1] – факт пометки числа m'+1 и т.д. Для каждой строки с номером y от 1 до [s'] (s' находится из 2s'(s'+1)=n') ищется такой столбец x, что S(x,y) – первое из чисел строки y, попадающее в интервал от m' до n': x=[(m'-y)/(2y+1)], причем, если x<y, то тогда, в силу симметричности таблицы относительно главной диагонали, берется x=y. Начиная с S(x,y) и получая каждое следующее число прибавлением числа d=2y+1 к предыдущему до тех пор, пока очередное число не превысит n', мы получаем числа, которые не являются основами простых чисел – эти числа отмечаются в битовом массиве. Для получения списка простых чисел после окончания анализа остается выбрать из массива все непомеченные основы N простых чисел 2N+1.