2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 16:23 
Этот код не плохо работает (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)
 

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 16:30 
Аватара пользователя
Код работает хорошо... Но неправильно. Спасибо, повеселили. guitar15, разница между полученным и верным результатами нам о чём-нибудь говорит?

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 16:44 
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, уже тут будет ошибка суммы, а время экономится. ;-)

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

(Оффтоп)

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

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

(Оффтоп)

rockclimber в сообщении #1233285 писал(а):
Имхо, при обсуждении кода лучше пользоваться тегом [tt]:
Да знаю, сначала вообще без тегов написал, потом теги расставлял мышкой, и ведь помнил и использую tt, а тут что-то переклинило. Но время ещё есть, сейчас поправлю, Вы правы, так красивее и понятнее.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 17:22 
код: [ скачать ] [ спрятать ]
Используется синтаксис 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())
 

Получилось.

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 17:25 
И сумма совпала? И время осталось порядка полуминуты? Прекрасно. 8-)

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 17:26 
Аватара пользователя
Сколько времени занимает расчёт? (У меня 13 с, сумма совпала.)

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

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 17:42 
Аватара пользователя

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

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


-- 13.07.2017, 17:55 --

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 23:00 
Dmitriy40, я хочу написать программу которая работает на методе решета Эратосфена с линейным временем работы, но я не могу понять псевдокод.

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

 
 
 
 Re: Найти сумму простых чисел на Python
Сообщение13.07.2017, 23:11 
Так там перед кодом словами объясняется, как он работает. Возьмите чистый лист бумаги, нарисуйте на нем ячейки массива, и вручную пройдите несколько итераций алгоритма. Бумага будет у вас отображать состояние памяти компьютера в процессе вычислений. Там все просто на самом деле, надо всего-то пять минут честно поработать руками.

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

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


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