Решето Александрова
Решето Александрова — это надёжный алгоритм вывода всех простых чисел до некоторого целого числа n. Он отличается от широко известного решета Эратосфена и более современного решета Аткина компактностью реализации на любом языке программирования. Основан же алгоритм на подходе, предложенном индийским математиком-студентом С.П.Сундарамом в 40-х годах XX в.
Формализацию этого общепризнанного метода осуществил Г.Александров , а многие российские и зарубежные исследователи создали на базе её удобные процедуры-фукции [см., например, http://tzone.mag.tc/projects/primes/js.html (автор - Стефан Легачёв)] :
Суть алогоритма такова: достаточно из натурального числового ряда исключить все значения
Z = i + j + 2 i j ,
где: i = 1 , 2 , 3 , ... , n ; j = 1 , 2 , 3 , ... i ,
а оставшиеся числа N умножить на 2 и прибавить 1. Это и будет ряд простых чисел p.
Программа на Yabasic выглядит так:
dim a(10000)
n=2000:a1=2:print a1;
for i=1 to n :for j=1 to i: a=i+j+2*i*j: if a<=2*n+1 then a(a)=1:fi:next j: next i
for k=1 to n: if a(k)=0 then
print 2*k+1;:fi:next k
С.Легачёв переписал алгоритм на JavaScript и его теперь можно встраивать в код html-страниц.
Функция совсем несложная:
function getPrimes (UpTo) {
*/
var selprimes = new Array();
var n = Math.floor( (UpTo - 1)/2 );
var result = new Array();
if (UpTo > 1) result[0] = 2;
for (i = 1; i <= UpTo; i++) {
selprimes[i] = true;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
if (i + j + 2*i*j <= UpTo) selprimes[i + j + 2*i*j] = false;
}
}
for (i = 1; i <= n; i++) {
if (selprimes[i] == true) result[result.length] = 2*i + 1;
}
return (result);
}
Еще проще процедура-функция будет выглядеть в математическом редакторе Maple.
Решето Александрова рекомендуется использовать в качестве стандартной подпрограммы.
Ссылки:
http://users.omskreg.ru/~project/SZ/z2/13.html
http://masterms.narod.ru/sundaram.html
.................................................
