2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Найти сумму простых чисел на Python
Сообщение11.07.2017, 16:09 


17/03/17
176
Всем привет. Нужно решить задачу.
Сумма простых чисел меньше $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 16:41 


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 17:04 
Заслуженный участник


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

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


17/03/17
176
нет :oops:

-- 11.07.2017, 18:18 --

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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 18:08 
Заслуженный участник


09/05/12
25179
guitar15 в сообщении #1232801 писал(а):
То есть нужно использовать NumPy?
В общем-то да. Или не Python, если это допустимо.

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение11.07.2017, 18:13 
Заслуженный участник
Аватара пользователя


16/07/14
8337
Цюрих
guitar15 в сообщении #1232807 писал(а):
в python отсутствуют массивы. Вместо них для хранения однородных (и не только) объектов используются списки
То, что в питоне называется list - и есть массив (в динамически типизированных языках).
Еще есть модуль array для типизированных массивов, они побыстрее. Но в данном случае непринципиально.

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 13:49 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
guitar15, позвольте полюбопытствовать, задачу нашли на Project Euler?

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


17/03/17
176
Да

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 15:41 


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 15:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 16:28 


17/03/17
176
У меня получился такой код (если я вас правильно понял), но время работы составляет 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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 16:55 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найти сумму простых чисел на Python
Сообщение12.07.2017, 18:05 
Заслуженный участник


20/08/14
11058
Россия, Москва
Аналог Вашего кода на дельфи (паскале) выполняется 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  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group