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

[guitar15]

Этот код не плохо работает (30-40 секунд), но ответа не совпал с $142913828922$
(у меня получилось $142915828925$)

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

a=2000000
sum=2
s=[2]
n=3
i=0
while n < a: 
    while i<=len(s):
        if n%s[i-1]==0:
            n+=2
            i=0
        i+=1
    sum_s=sum+n
    sum=sum_s
    if n**2<=a:
        s.append(n)
        n+=2
        i=0
    else:
        n+=2
        i=0
print(sum_s)
 

[Aritaborian]

Код работает хорошо... Но неправильно. Спасибо, повеселили. guitar15, разница между полученным и верным результатами нам о чём-нибудь говорит?

[Dmitriy40]

s=[2] лишнее, на двойку и так уже всё проверено, достаточно s=[].
В последнем if занимательно смотреть на дублирование одинакового кода в обеих ветвях.
Зачем sum и sum_s до меня по прежнему не доходит.
Вместо len(s) я бы завёл ещё переменную равную len(s) в каждый момент времени и сравнивал с ней. Может быть выигрыш во времени. Увеличить её легко вместе с s.append.
Формально условие n<a неправильное, надо n<=a, как раньше и было, это будет важно для простых величин a (вдруг захотите в будущем посчитать не до 2 миллионов).
Разве допустимо выражение s[-1]? А оно у вас в строке n%s[i-1] обязательно будет, и не один раз. Да и s[0] лично мне под вопросом, не знаю с чего (0 или 1) нумеруются списки в питоне.
Ну и плюс неправильное условие остановки в самом конце, из-за чего и сумма неправильная. Эта же причина и в предыдущем коде была.
PS. Проверять правильность кода можно для a=10, уже тут будет ошибка суммы, а время экономится.

[rockclimber]

(Оффтоп)

Dmitriy40 в сообщении #1233279 писал(а):

s=[2] лишнее, на двойку и так уже всё проверено, достаточно s=[].

Имхо, при обсуждении кода лучше пользоваться тегом [tt]:
"s=[2] лишнее, на двойку и так уже всё проверено, достаточно s=[]"

[Dmitriy40]

(Оффтоп)

rockclimber в сообщении #1233285 писал(а):

Имхо, при обсуждении кода лучше пользоваться тегом [tt]:

Да знаю, сначала вообще без тегов написал, потом теги расставлял мышкой, и ведь помнил и использую tt, а тут что-то переклинило. Но время ещё есть, сейчас поправлю, Вы правы, так красивее и понятнее.

[guitar15]

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

def number():
    a=2000001
    m=2
    s=[2]
    n=3
    i=1
    while n <=a: 
        while i<=len(s):
            if n%s[i-1]==0:
                n+=2
                if n>=a:
                    return sum
                i=1
            i+=1
        sum=m+n
        m=sum
        if n**2<=a:
            s.append(n)
            i=1
        n+=2
        i=1
    return sum
print(number())
 

Получилось.

[Dmitriy40]

И сумма совпала? И время осталось порядка полуминуты? Прекрасно.

[Aritaborian]

Сколько времени занимает расчёт? (У меня 13 с, сумма совпала.)

[guitar15]

20 с

[Dmitriy40]

С решетом Эратосфена будете разбираться или достигнутый результат устраивает? Оно ещё проще этого кода, там всего два простых вложенных цикла (плюс отдельный цикл начальной инициализации).

[Aritaborian]

(Бу-бу-бу про PEP 8)

В Питоне приняты правила насчёт пробелов рядом со знаками бинарных операций. Ознакомьтесь с ними. (Разумеется, остальная часть этих рекомендаций по оформлению кода также очень полезна.)

-- 13.07.2017, 17:55 --

Dmitriy40 в сообщении #1233279 писал(а):

не знаю с чего (0 или 1) нумеруются списки в питоне

С нуля.
guitar15, идеологически более верно было бы определять функцию number(a) и вычислять затем number(2000000), а то вообще непонятно, зачем это как функцию оформлять. Ну то есть, либо одно либо другое.

[guitar15]

Dmitriy40, я хочу написать программу которая работает на методе решета Эратосфена с линейным временем работы, но я не могу понять псевдокод.

[arseniiv]

Псевдокод, конечно, писал какой-то грамотей (pr[] += {i} — мда), но по предшествующему описанию можно понять, что он означает. А какие конкретные вопросы?

[rockclimber]

Так там перед кодом словами объясняется, как он работает. Возьмите чистый лист бумаги, нарисуйте на нем ячейки массива, и вручную пройдите несколько итераций алгоритма. Бумага будет у вас отображать состояние памяти компьютера в процессе вычислений. Там все просто на самом деле, надо всего-то пять минут честно поработать руками.

[Dmitriy40]

guitar15
Псевдокод решета Эратосфена:
1. заполняем массив с индексами от 2 до max единицами;
2. идём индексом n по массиву от 2 до max и выполняем следующее:
3. для каждого индекса n если число в массиве равно 1, то оно простое и тогда выполняем следующее:
4. идем по массиву индексом i начиная с n до max/n и обнуляем элемент массива с идексом i*n.
Всё.
Пункт 4 будет выполнен лишь для простых чисел в диапазоне от 2 до max и вычеркнет все числа, делящиеся на каждое найденное простое число n т.е. составные. Туда же можно и вычисление суммы добавить. Сами найденные простые в Вашей задаче сохранять не нужно.
Куда уж проще писать и не знаю даже.