2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 14:52 
У меня получилось 5 с.
код: [ скачать ] [ спрятать ]
Используется синтаксис Python
number = 2000000
s = [0,0]
a=0
for  index  in range(2,number+1):
   s.append(1)
for n in range(2,len(s)):
    if s[n]==1:
        s[n]=n
        m=a+n
        a=m
        i=n
        max=len(s)/n
        while i<max:
            s[n*i]=0
            i+=1
print(m)
 

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 15:04 
Аватара пользователя
Не по задаче, но про Питон. Создавать список, заполненный единицами, можно (и нужно) с помощью list comprehension:
Используется синтаксис Python
s = [1 for i in range(2, number + 1)]

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 15:23 
Aritaborian, спасибо.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 15:31 
Всё же мне очень интересны причины возникновения переменной m? Почему не просто a+=n?
Непонятна так же команда s[n]=n - зачем? Ведь дальше никак не используется.
Плюс, если есть желание, можно проверить насколько будет (и будет ли) быстрее последний цикл в форме
Используется синтаксис Python
         i=n*n
         while i<=number:
             s[i]=0
             i+=n
Т.е. без умножения в цикле.
Ну и знак у Вас неправильный, должен быть именно <=, иначе можете не вычернуть последнее составное число равное степени простого, что приведёт к ошибке.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 16:41 
Цитата:
Плюс, если есть желание, можно проверить насколько будет (и будет ли) быстрее последний цикл в форме

К сожалению, если сделать замену последнего цикла программа перестанет работать.
s[i]=0
IndexError: list assignment index out of range

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 17:03 
Забавно. Чего-то я недопонимаю. Или Вы ошиблись в коде. Потому что на дельфи у меня оба варианта работают одинаково.

(Скорость простого цикла)

Забавно что на дельфи первый вариант цикла, с умножением внутри цикла, работает в полтора раза быстрее. Что в общем-то противоречит правилам оптимизации алгоритмов. И это не глюк компилятора, я смотрел по асм коду, умножение реально в теле цикла стоит. Думаю это связано с тонкостями устройства процессора, с умножением итерации цикла процессору кажутся почему-то более независимыми и он выполняет их одновременно. Вероятно можно и ещё ускорить если цикл частично развернуть, но это уже ненужные (тем более на питоне!) тонкости.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 17:16 
Вот еще вариант:
Используется синтаксис Python
def sieve(n):
    notprime = set()
    for i in range(2,n):
        if i not in notprime:
            yield i
            notprime |= set(range(i*i,n+1,i))
print(sum(sieve(2000000)))

Заодно тут можно углядеть всякие клевые возможности питона, упрощающие жизнь.
Aritaborian в сообщении #1233525 писал(а):
Создавать список, заполненный единицами, можно (и нужно) с помощью list comprehension:

Лучше так:
Используется синтаксис Python
[1]*(number-1)

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 17:47 
Dmitriy40, вот код.
код: [ скачать ] [ спрятать ]
Используется синтаксис Python
import time
start = time.time()
number = 2000000
s = [0,0]
a=0
s = [1 for i in range(2, number + 1)]
for n in range(2,len(s)):
    if s[n]==1:
        a+=n
        i=n*n
        while i<=number:
            s[i]=0
            i+=n
print(a)
end = time.time()
print(end - start)
 

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение14.07.2017, 17:47 
Аватара пользователя
12d3 в сообщении #1233556 писал(а):
Лучше так
Разумеется; а я что-то затупил. Будем, однако, надеяться, что информация по list comprehensions окажется для ТС полезной ;-)

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение15.07.2017, 01:10 
Аватара пользователя
12d3 в сообщении #1233556 писал(а):
Лучше так
Только после осознания разницы между mutable и immutable. А то замена 1 на [] приведет к неприятным сюрпризам.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение15.07.2017, 01:51 
Я так и не понял, последний выложенный код заработал правильно (с правильной суммой) или нет? И если да, то изменилась ли скорость работы? А если нет, то в чём же проблема?

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение15.07.2017, 09:43 
Цитата:
Я так и не понял, последний выложенный код заработал правильно (с правильной суммой) или нет? И если да, то изменилась ли скорость работы? А если нет, то в чём же проблема?

Он не работает.
s[i]=0
IndexError: list assignment index out of range

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


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