Целое число, большее 1, называется простым, если оно не делится нацело ни на какое другое, кроме себя и 1.
Древний алгоритм «Решето Эратосфена» для поиска всех простых чисел до n выглядит так:
- Создать список последовательных чисел от
2доn:2, 3, 4, ..., n. - Пусть
p=2, это первое простое число. - Зачеркнуть все числа в списке с разницей в
p, т.е.2p, 3p, 4pи т.д. В случаеp=2это будут2,4,6,8.... - Поменять значение
pна первое незачеркнутое число послеp. - Повторить шаги 3-4 пока
p2 < n. - Все оставшиеся незачеркнутыми числа - простые.
Посмотрите также анимацию алгоритма.
Реализуйте «Решето Эратосфена» в JavaScript. Найдите все простые числа до 100 и выведите их сумму.
Решение
#181