Решето Сундарама

Поиск простых чисел   12 июня 2012  Автор статьи:  

Решето Сундарама — алгоритм поиска простых чисел.
Описание алгоритма:
Алгоритм построен на идее вычеркивания всех составных чисел, после чего остаются лишь простые.
Вычеркивание чисел происходит следующим образом:
Выписываются все натуральные числа от 1 до n.
Далее вычеркиваются все числа равные i+j+2*i*j, где i и j — все возможные сочетания чисел от 1 до n, причем всегда i<=j.
Все оставшиеся не зачеркнутыми числа умножаются на два и увеличиваются на единицу.
В итоге остаются только простые числа.
Пример работы алгоритма для n = 50:
1. Выписываем все числа от 1 до 50.
 

 
2. Вычеркиваем все числа равные i+j+2*i*j, где i<=j<=n.   При i = 1 и 1<=j<=50.  
 
При i = 2 и 2<=j<=50.  
 
При i = 3 и 3<=j<=50.  
 
Дальнейшее увеличение i и j не требуется, т.к. i+j+2*i*j будет больше 50.
 
3. Умножаем все оставшиеся числа на 2 и прибавляем единицу. Получаем все простые числа из диапазона от 1 до 2*50+1 = 101.
 

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++