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

[guitar15]

У меня получилось 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)
 

[Aritaborian]

Не по задаче, но про Питон. Создавать список, заполненный единицами, можно (и нужно) с помощью list comprehension:

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

s = [1 for i in range(2, number + 1)]

[guitar15]

Aritaborian, спасибо.

[Dmitriy40]

Всё же мне очень интересны причины возникновения переменной m? Почему не просто a+=n?
Непонятна так же команда s[n]=n - зачем? Ведь дальше никак не используется.
Плюс, если есть желание, можно проверить насколько будет (и будет ли) быстрее последний цикл в форме

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

         i=n*n
         while i<=number:
             s[i]=0
             i+=n

Т.е. без умножения в цикле.
Ну и знак у Вас неправильный, должен быть именно <=, иначе можете не вычернуть последнее составное число равное степени простого, что приведёт к ошибке.

[guitar15]

Цитата:

Плюс, если есть желание, можно проверить насколько будет (и будет ли) быстрее последний цикл в форме

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

[Dmitriy40]

Забавно. Чего-то я недопонимаю. Или Вы ошиблись в коде. Потому что на дельфи у меня оба варианта работают одинаково.

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

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

[12d3]

Вот еще вариант:

Используется синтаксис 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)

[guitar15]

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)
 

[Aritaborian]

12d3 в сообщении #1233556 писал(а):

Лучше так

Разумеется; а я что-то затупил. Будем, однако, надеяться, что информация по list comprehensions окажется для ТС полезной ;-)

[mihaild]

12d3 в сообщении #1233556 писал(а):

Лучше так

Только после осознания разницы между mutable и immutable. А то замена 1 на [] приведет к неприятным сюрпризам.

[Dmitriy40]

Я так и не понял, последний выложенный код заработал правильно (с правильной суммой) или нет? И если да, то изменилась ли скорость работы? А если нет, то в чём же проблема?

[guitar15]

Цитата:

Я так и не понял, последний выложенный код заработал правильно (с правильной суммой) или нет? И если да, то изменилась ли скорость работы? А если нет, то в чём же проблема?

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