2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Найти сумму простых чисел на Python
Сообщение11.07.2017, 16:09 
Всем привет. Нужно решить задачу.
Сумма простых чисел меньше $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$ нужно очень долго ждать результата(я не дождался). Как оптимизировать программу?

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 16:41 
То есть нужно использовать NumPy?

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 17:04 
Зачем? Нужен одномерный массив, надеюсь, такие есть в питоне.
Вы вот этот код понимаете: в википедии

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 17:13 
нет :oops:

-- 11.07.2017, 18:18 --

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 18:08 
guitar15 в сообщении #1232801 писал(а):
То есть нужно использовать NumPy?
В общем-то да. Или не Python, если это допустимо.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 18:13 
Аватара пользователя
guitar15 в сообщении #1232807 писал(а):
в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки
То, что в питоне называется list - и есть массив (в динамически типизированных языках).
Еще есть модуль array для типизированных массивов, они побыстрее. Но в данном случае непринципиально.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 13:49 
Аватара пользователя
guitar15, позвольте полюбопытствовать, задачу нашли на Project Euler?

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 14:32 
Да

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 15:41 
Думаю, что для нахождения простых чисел можно использовать Решето Эратосфена с линейным временем работы. К сожалению, я не могу понять как использовать этот метод.

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 16:28 
У меня получился такой код (если я вас правильно понял), но время работы составляет 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)
 

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

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

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

-- 12.07.2017, 18:39 --

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

 
 
 [ Сообщений: 42 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group