Задача формирования списка простых чисел относится к тем задачам, на примере которых наглядно демонстрируется эффективность использования множеств.
Условие задачи. Требуется найти все простые числа в диапазоне 2 .. , где > 2.
По определению, к простым относятся такие числа, которые делятся без остатка только на 1 и сами на себя.
Выполним поиск простых чисел в диапазоне 2 .. 10000, используя приведенное выше определение.
Program Prime1;
Const n = 10000;
TypePrimeAr = array[1 .. n div 2] of word;
Var i,j,
NextPrime, { очередное простое число }
m, { кол-во простых чисел }
p : word;
Primes : PrimeAr; { массив простых чисел }
Cond : boolean;
Begin
Primes[1]:=2; m:=1;
Fori:=3 to n do
Begin
NextPrime:=i; p:=NextPrime div 2;
Cond:=true;
Forj:=1 tom do
If NextPrime mod Primes[j]=0 then
Begin
Cond:=false; Break { выход за пределы цикла по j }
End
Else
IfPrimes[j]>p then
Break; { выход за пределы цикла по j }
IfCond then
Begin
Inc(m); Primes[m]:=NextPrime
End;
End;
Печать массива Primes
End.
Количество простых чисел в диапазоне 2 .. n по крайней мере не превосходит значения n/2. Поэтому размер массива Primes принят равным n div2.
В массиве Primes накапливается список простых чисел. В цикле по i производится перебор элементов числовой последовательности 3, 4, ..., n. Очередное число NextPrime, взятое из этой последовательности, делится в цикле по j на числа, накопленные к этому моменту в массиве Primes. Если остаток от деления равен нулю, то это означает, что значение NextPrime не является простым числом. Тогда дальнейший перебор массива Primes прекращается. Выход из цикла по j производится также в том случае, когда очередное число из массива Primes превышает значение p, равное NextPrime div 2. Если после окончания работы цикла по j переменная Cond сохранит значение true, то производится добавление в список простых чисел значения переменной NextPrime.
Основным недостатком программы Prime1 является то, что при проверке каждого значения переменной NextPrime многократно выполняется операция деления, требующая значительных затрат машинного времени.
Для формирования списка простых чисел наиболее эффективным является алгоритм, называемый "решето Эратосфена". Преимуществом этого алгоритма является то, что в нем для нахождения простых чисел не нужно использовать операции умножения и деления.
Последовательность работы алгоритма:
Шаг 1. Поместить все числа от 2 до n в "решето".
Шаг 2. Выбрать и удалить из "решета" наименьшее число.
Шаг 3. Поместить это число среди простых чисел.
Шаг 4. Удалить из "решета" все числа, кратные данному.
Шаг 5. Если "решето" не пустое, то перейти к шагу 2.
Проиллюстрируем работу алгоритма на конкретном примере. Для этого в качестве решета будем использовать массив Sieve, а для списка простых чисел, как и в программе Prime1, - массив Primes.
Вначале реализуем алгоритм Эратосфена без использования множеств. При этом удаляемым из массива Sieve числам будем присваивать нулевое значение (это более эффективно, чем сдвиг подмассива влево для удаления очередного числа).
Примечание. Такая форма условного удаления числа из массива допустима лишь в том случае, когда в исходном массиве не может быть нулевых чисел.
ProgramPrime2;
Constn = 10000;
TypeSieveAr = array[2..n] of word;
PrimeAr = array[1..(n div2)] of word;
Var i,j,
NextPrime, { очередное простое число }
Multiple, { множитель, кратный NextPrime }
m : word; { кол-во простых чисел }
Primes : PrimeAr; { массив простых чисел }
Sieve : SieveAr; { "решето" натуральных чисел }
Cond : boolean;
Begin
Fori:=2 ton do { размещение чисел в "решете" }
Sieve[i]:=i;
Cond:=true; m:=0;
WhileCond do
Begin
NextPrime:=0;
For i:=2 to n do{ нахождение минималь- }
IfSieve[i]<>0 then{ ного числа в массиве }
Begin{ Sieve }
NextPrime:=i; Break
End;
If NextPrime=0 then { если NextPrime=0, то }
Cond:=false { "решето" - пустое }
Else
Begin
Inc(m); { добавление очередного }
Primes[m]:=NextPrime; { числа в массив Primes }
Multiple:=NextPrime-1;
While Multiple<=n do { удаление из решета чи-}
Begin{ сел, кратных значению }
Sieve[Multiple]:=0; { NextPrime }
Inc(Multiple,NextPrime);
End;
End;
End;
Печать массива Primes
End.
Программа Prime2 работает значительно быстрее, чем программа Prime1, поскольку в ней не используются операции умножения и деления. Однако здесь для реализации алгоритма применены два больших массива Sieve и Primes, каждый элемент которых занимает два байта памяти.
Реализация алгоритма Эратосфена с использованием множеств:
Оба множества Sieve и Primes - это битовые строки длиной бит. На стартовом участке программы все биты множества Sieve устанавливаются в положение 1, все биты множества Primes - в положение 0. В дальнейшем при нахождении очередного простого числа один бит в Primes устанавливается в положение 1, а часть бит в Sieve (биты, соответствующие кратным значениям простого числа) - в положение 0.
Каждый элемент множеств Sieve и Primes занимает один бит памяти, т.е. в 16 раз меньше, чем элементы массивов Sieve и Primes в программе Prime2. Программа Prime3 одновременно требует меньших затрат машинного времени по сравнению с программой Prime2, поскольку обработка битовых строк осуществляется быстрее, чем обработка числовых массивов.
Следует отметить, что при заданном значении = 10000 программа Prime3 работать не будет, так как при этом мощность множества превышает максимально допустимое значение = 256. Чтобы обеспечить генерацию простых чисел при > 256, необходимо представить "решето" и последовательность простых чисел в виде массива множеств, что приведет к небольшому усложнению программы.
, где 
бит. На стартовом участке программы все биты множества Sieve устанавливаются в положение 1, все биты множества Primes - в положение 0. В дальнейшем при нахождении очередного простого числа один бит в Primes устанавливается в положение 1, а часть бит в Sieve (биты, соответствующие кратным значениям простого числа) - в положение 0.