2014 dxdy logo

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

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




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


17/03/17
176
У меня получилось 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 
Аватара пользователя


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

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


17/03/17
176
Aritaborian, спасибо.

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


20/08/14
11070
Россия, Москва
Всё же мне очень интересны причины возникновения переменной 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 


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

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

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


20/08/14
11070
Россия, Москва
Забавно. Чего-то я недопонимаю. Или Вы ошиблись в коде. Потому что на дельфи у меня оба варианта работают одинаково.

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

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

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


04/03/09
906
Вот еще вариант:
Используется синтаксис 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 


17/03/17
176
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 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
12d3 в сообщении #1233556 писал(а):
Лучше так
Разумеется; а я что-то затупил. Будем, однако, надеяться, что информация по list comprehensions окажется для ТС полезной ;-)

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


16/07/14
8355
Цюрих
12d3 в сообщении #1233556 писал(а):
Лучше так
Только после осознания разницы между mutable и immutable. А то замена 1 на [] приведет к неприятным сюрпризам.

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


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

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


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3

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



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

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


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

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