Условие задачи
Мы уже использовали алгоритмы поиска простых чисел на python здесь и здесь. Но в этой задаче я хочу попробовать нечто новое - Решето Эратосфена . Это достаточно интересный и быстрый алгоритм, но я его не использовал в прошлых задачах т.к они не сильно подходили под условия - здесь же решето Эратосфена подходит практически идеально.
На заметку - недавно вычитал из статьи на Хабре, что один известный математик недавно оптимизировал решето Эратосфена. Речь идет о очень существенной экономии памяти - буквально с гигабайта к мегабайту. Если где-то опубликуют его алгоритм обязательно напишу об этом статью.
В данной программе я использовал 2 функции
eratosthen(n) - пропускаем через решето массив от 0 до числа n. Функция создает массив, а затем в цикле заполняем нулями числа согласно правил решета Эратосфена
sum - встроенная функция суммирования списков
Полный текст программы
def eratosthen(n):
sieve = list(range(n))
sieve[1] = 0
for i in sieve[2:]:
for j in range(i + i, len(sieve), i):
sieve[j] = 0
return sieve
print(sum(eratosthen(2000000)))
Сумма простых чисел меньше 10 - это 2 + 3 + 5 + 7 = 17.
Найдите сумму всех простых чисел меньше двух миллионов.
Решение
Мы уже использовали алгоритмы поиска простых чисел на python здесь и здесь. Но в этой задаче я хочу попробовать нечто новое - Решето Эратосфена . Это достаточно интересный и быстрый алгоритм, но я его не использовал в прошлых задачах т.к они не сильно подходили под условия - здесь же решето Эратосфена подходит практически идеально.
На заметку - недавно вычитал из статьи на Хабре, что один известный математик недавно оптимизировал решето Эратосфена. Речь идет о очень существенной экономии памяти - буквально с гигабайта к мегабайту. Если где-то опубликуют его алгоритм обязательно напишу об этом статью.
В данной программе я использовал 2 функции
eratosthen(n) - пропускаем через решето массив от 0 до числа n. Функция создает массив, а затем в цикле заполняем нулями числа согласно правил решета Эратосфена
sum - встроенная функция суммирования списков
Полный текст программы
def eratosthen(n):
sieve = list(range(n))
sieve[1] = 0
for i in sieve[2:]:
for j in range(i + i, len(sieve), i):
sieve[j] = 0
return sieve
print(sum(eratosthen(2000000)))
Задача решена