Найти сумму простых чисел на Python

[guitar15]

Всем привет. Нужно решить задачу.
Сумма простых чисел меньше $10$ $\text{~---}$ это $2 + 3 + 5 + 7 = 17$.
Найдите сумму всех простых чисел меньше двух миллионов.
Для решения я использую метод решета Эратосфена(код внизу).

Используется синтаксис Python

a=2000001
s=list(range(2,a))
s_sum=0
for i in s:
    if i**2<a:        
        k=0
        while k<len(s):
            if s[k]==i:
                k+=1
            elif s[k]%i==0:
                s.remove(s[k])
                k+=1
            else:
                k+=1
    s_sum=s_sum+i
print(s_sum)
 

Этот скрипт не плохо работает для чисел меньших $2\cdot 10^4$, но для $2\cdot 10^6$ нужно очень долго ждать результата(я не дождался). Как оптимизировать программу?

[venco]

Решето Эратосфена работает хорошо, если использовать не список чисел, как у вас, а массив флагов простое/составное, по одному флагу на каждое число. Даже в википедии есть достаточно разумный псевдо-код, используйте его.
В вашем коде медленные операции поиска в списке удаляемых элементов. С массивом это будут элементарные операции выборки по кратным индексам.

[guitar15]

То есть нужно использовать NumPy?

[venco]

Зачем? Нужен одномерный массив, надеюсь, такие есть в питоне.
Вы вот этот код понимаете: в википедии

[guitar15]

нет

-- 11.07.2017, 18:18 --

Я не знаю, как создать массив (в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки. )

[Pphantom]

guitar15 в сообщении #1232801 писал(а):

То есть нужно использовать NumPy?

В общем-то да. Или не Python, если это допустимо.

[mihaild]

guitar15 в сообщении #1232807 писал(а):

в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки

То, что в питоне называется list - и есть массив (в динамически типизированных языках).
Еще есть модуль array для типизированных массивов, они побыстрее. Но в данном случае непринципиально.

[Aritaborian]

guitar15, позвольте полюбопытствовать, задачу нашли на Project Euler?

[guitar15]

Да

[guitar15]

Думаю, что для нахождения простых чисел можно использовать Решето Эратосфена с линейным временем работы. К сожалению, я не могу понять как использовать этот метод.

[Dmitriy40]

Для чисел до 2 миллионов можно не связываться с решетом (раз уж не понимаете его), сделать проверку каждого нечётного числа на простоту делением на все простые до корня из проверяемого числа. При нахождении нового простого числа добавлять его в список проверочных (если его квадрат меньше 2 миллионов) и добавлять его к сумме. Всё. Понадобится не более 223 миллионов делений (даже заметно меньше), это пара секунд, остальные операции ещё быстрее (проход списка подряд вперёд не медленнее прямого обращения в массив).

[guitar15]

У меня получился такой код (если я вас правильно понял), но время работы составляет 4 минуты.

Используется синтаксис Python

s=[]
s_sum=0
n=2
while n<=2000000:
    k=2
    while k<=n**0.5:
        if n%k==0:
            n+=1
            k=2
        else:
            k+=1
    s.append(n)
    sum=s_sum+n
    s_sum=sum
    n+=1
print(sum)
 

[mihaild]

guitar15, попробуйте перебирать не все k, а только уже найденные простые. Еще полученный код может неправильно работать для точных квадратов (вещественный корень может оказаться чуть меньше правильного значения). Ну и вместо сложной логики "на каждой итерации ищем следующее простое" можно сделать гораздо проще "проверяем, является ли текущее число простым" (т.е. n внутри цикла по k не менять - и вообще по нему сделать for n in range(2, 2*10^6)).

[Dmitriy40]

Нет необходимости вычислять корень для каждого прохода цикла по k, достаточно запустить цикл прохода по всему накопленному массиву s, ведь там именно нужные числа и есть. А вот добавлять туда числа не все найденные, а лишь если их квадрат меньше 2 миллионов. У Вас основные тормоза в операции извлечения корня. Плюс проход по k должен идти не по всем числам подряд, а лишь по числам из списка s, это вшестеро ускорит программу.
Плюс ускорить вдвое можно если n начинать с 3 и увеличивать на 2, ведь проверять чётные числа (кроме 2) нет смысла.
В итоге ускорение будет минимум 12 раз, а на самом деле раз 30-50 (возведение в степень 0.5 медленнее деления).
Чем отличаются переменные sum и s_sum до меня не доходит.

[Dmitriy40]

Аналог Вашего кода на дельфи (паскале) выполняется 1.5 секунды (причём сумма неправильная!), после предложенных модификаций время 0.18 секунды, ускорение больше 8-ми раз, значит можно ожидать времени в полминуты на питоне. Решето Эратосфена без всяких оптимизаций выполняется за 0.06 секунды, ещё втрое быстрее. Ну и "скорость" питона видно.
Для проверки: правильная сумма равна $142913828922$.

-- 12.07.2017, 18:39 --

Ещё пара цифр, для чисел до 20 миллионов время выполнения программы (Ваша : оптимизированная : решето): 33с : 3.1с : 0.42с.
До 200 миллионов (аналогично): 894с : 62с : 4.9с.