Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n.
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
1.Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2.Пусть переменная p изначально равна двум — первому простому числу.
3.Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
4.Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5.Повторять шаги 3 и 4, пока возможно.
Используя переменную i вместо p, за основу возьмем усовершенствованный алгоритм, когда на шаге № 3 числа можно зачеркивать начиная сразу с квадрата числа i, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда квадрат i станет больше, чем n
Вложение:
Решето.JPG [ 108.66 КБ | Просмотров: 7831 ]
В редакторе DrakonBar используем генератор "Processing.org"
Вложение:
Решето2.JPG [ 77.23 КБ | Просмотров: 7831 ]
Код:
// Generator adopted by Bardynin Dmitry, Astrakhan-Sochi, 2019, ver.0.11
// Resheto AEratosfena
void setup( ) {
int n = 100000000;
//Sozdaem massiv n-jacheek
boolean[] a = new boolean[n+1];
int i = 2;
while (true) {
a[i] = true;
i = i + 1;
if (i<=n) {
} else {
break;
}
}
i = 2;
while (true) {
if (a[i] == true) {
int j = i*i;
while (true) {
a[j] = false;
j = j + i;
if (j <= n) {
} else {
break;
}
}
} else {
}
i = i + 1;
if (i*i <= n) {
} else {
break;
}
}
i = 2;
while (true) {
if (a[i] == true) {
print('\t'); // output_simple
print(i); // output_simple
} else {
}
i = i + 1;
if (i<=n) {
} else {
break;
}
}
}
void draw () {}
