Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
0 / 0 / 0
Регистрация: 16.10.2010
Сообщений: 11
1

Поиск простых чисел выполняется слишком долго

01.07.2014, 18:09. Показов 2673. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день,

На Лурке в статье Python (http://lurkmore.to/Python)

Приводится код скрипта - поиск простых чисел от 1 до 1 000 0000 и запись найденных в файлик
Выполнение данного скрипта у меня заняло 5 минут с гаком.

Скажите, пожалуйста, ведь это очень долго, я правильно понимаю?

Еще у них есть приписка: "Шах и мат"
Есть у кого какие мысли на этот счет? Что они имели в виду?


Код привожу ниже.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import time # тут библиотека времени
import math # а вот это считает корни и прочий матан
out=open('outfile.txt','w') # ясно же, что с файло работать будем
out.write('Первый нах посчитал от 1 and 10 000\n-----\n а чего добился ты ?')
start = time.time()
print "2\n3\n5\n7\n11\n13\n17\n19\n23\n"
out.write( "2\n3\n5\n7\n11\n13\n17\n19\n23\n") ## Это выкидывает перечисленные числа сразу, это круто, экономит нам 0.04 секунды при расчёте до 1000000
for i in range (17,1000000,2):
    if ( 
    i%2 ==  0 or# |(                                                                     )
    i%3 ==  0 or# |(                                                                     )
    i%5 ==  0 or# |(                                                                     )
    i%7 ==  0 or# |(   быстренько проверим на первые простые,                            )
    i%11 == 0 or# |(   массив можно продолжать до усрачки                                )
    i%13 == 0 or# |(                                                                     )
    i%17 == 0 or# |(                                                                     )
    i%19 == 0 or# |(                                                                     )
    i%23 == 0   # |(                                                                     )
    ):
        continue
    # если реально похоже на простое, подозрительно щуримся и проверяем его решетом ->    
    else:
        easy=True
        for j in range (3,int(math.sqrt(i)+1),2): # нафиг все чётные
            if i%j==0:
                easy=False
        if easy==True:
            print i
            out.write(str(i)+"\n")
 
finish = time.time()
print (str (finish - start))
out.write('Program work at '+str (finish - start)+' second') # тут запишем время выполнения
out.close #файлы после окончания всех манипуляций, вроде как, надо закрывать
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.07.2014, 18:09
Ответы с готовыми решениями:

Задача не проходит по времени, слишком долго выполняется
Условие: Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой...

Решето Эратосфена выполняется слишком долго
Следующий код... eratosPrimes :: Int -> eratosPrimes n = getEratosPrimes n where ...

Слишком долго выполняется запрос и возвращаются строки из БД
Здравствуйте. Я переделываю программу для знакомых. У них были исходники и они мне их дали для...

Сохранение страниц выполняется слишком долго, и текст обрезается
Здравствуйте! Помогите пожалуйста решить следующую проблему. Сайт на wp. Сервер apache 2.2...

Интегрирование заданной функции тремя способами - код выполняется слишком долго
Добрый вечер! Надо сделать лабораторную работу по численным методам. Результат верный, но программа...

10
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
01.07.2014, 18:17 2
Кэп подсказывает, что лурк - последнее место для изучения программирования.
0
0 / 0 / 0
Регистрация: 16.10.2010
Сообщений: 11
01.07.2014, 18:34  [ТС] 3
Это понятно, а по-существу вопроса, что можете сказать?

Это долго или нет?
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
01.07.2014, 18:46 4
Долго. Но и алгоритм тут - тупой перебор, что с него взять? См решето Эратосфена.
0
0 / 0 / 0
Регистрация: 16.10.2010
Сообщений: 11
01.07.2014, 22:37  [ТС] 5
Я могу ошибаться, но по-моему, когда я считал в интерпритаторе 2 в степени 1 000 000 он и то быстрее справился
0
26 / 26 / 6
Регистрация: 19.10.2012
Сообщений: 131
02.07.2014, 02:31 6
Цитата Сообщение от zamiel Посмотреть сообщение
когда я считал в интерпритаторе 2 в степени 1 000 000 он и то быстрее справился
деленеие выполняется несколько дольше в машинной арифметике, нежели умножение. А уж проверка делением на большое количество различных чисел ещё более ресурсоёмко. У вас весьма странные представления.
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
02.07.2014, 06:30 7
Цитата Сообщение от zamiel Посмотреть сообщение
Я могу ошибаться, но по-моему, когда я считал в интерпритаторе 2 в степени 1 000 000 он и то быстрее справился
При условии, что считали умножением в цикле, сложность O(n). В коде из первого поста грубо говоря (совсем грубо) верхняя оценка будет O(n^2).
0
Эксперт Python
4632 / 2050 / 361
Регистрация: 17.03.2012
Сообщений: 10,134
Записей в блоге: 6
02.07.2014, 07:39 8
Ну видно же, что для каждого i прога запускает большой цикл. Проверяется каждое число отдельно. Ещё бы оно быстро работало.
Решето Эратосфена - это совсем не то, оно предназначено для отсеивания простых на большом участке.
0
117 / 101 / 53
Регистрация: 13.04.2014
Сообщений: 233
02.07.2014, 15:27 9
Я бы заменил:
Цитата Сообщение от zamiel Посмотреть сообщение
Python
1
2
if i%j==0:
    easy=False
на
Python
1
easy = i%j
и
Цитата Сообщение от zamiel Посмотреть сообщение
Python
1
if easy==True:
на
Python
1
if easy:
Цитата Сообщение от zamiel Посмотреть сообщение
Python
1
2
3
for i in range (17,1000000,2):
    if ( 
    i%2 == 0
чётного числа тут быть не может так i%2 это можно убрать.
0
21 / 21 / 7
Регистрация: 24.01.2013
Сообщений: 129
03.07.2014, 12:24 10
на самом деле - это троллинг питона, так как он язык интерпретуриемый и не может достичь скорости компилируемых
а чтобы работало значительно дольше, они еще и алгоритм взяли заведомо плохой

рекомендую воспользоваться решетом Эратосфена, скорость будет на порядок выше, также посмотреть один из вариантов можно и здесь http://habrahabr.ru/post/122538/

Добавлено через 5 минут
на явный под*еб питона как бы намекают эти строки:
if (
i%2 == 0 or# |( )
i%3 == 0 or# |( )
i%5 == 0 or# |( )
i%7 == 0 or# |( быстренько проверим на первые простые, )
i%11 == 0 or# |( массив можно продолжать до усрачки )
i%13 == 0 or# |( )
i%17 == 0 or# |( )
i%19 == 0 or# |( )
i%23 == 0 # |( )
):
и вот это особенно, так не пишут: print (str (finish - start))

Добавлено через 43 минуты
решето Аткина тоже посмотрите
0
10 / 10 / 4
Регистрация: 16.06.2014
Сообщений: 45
06.07.2014, 01:04 11
Алгоритм явно долгий. Существует решето Эратосфена, работающее за О(N log N), также рекомендую обратить внимание на тесты на простоту, например, тест Миллера-Рабина. Описания можно найти на e-maxx.ru/algo и на Википедии.

Вообще - питон довольно быстр, если правильно им пользоваться
0
06.07.2014, 01:04
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.07.2014, 01:04
Помогаю со студенческими работами здесь

Слишком долго выполняется задача "ка-тая банка"
Привет. У Никиты есть n банок газировки, каждая из которых имеет свой объём. Известно, что...

Сумма всех простых чисел меньше двух миллионов - очень долго вычисляется
Приветствую! Решал задачки Эйлера и наткнулся на эту: Сумма простых чисел меньше 10 равна 2 +...

Поиск всех простых чисел в интервале чисел, разделенном на несколько диапазонов
Поиск всех простых чисел в указанном интервале чисел, разделенном на несколько диапазонов....

Поиск простых чисел среди чисел Фибоначчи с использованием событий
Доброе время суток! Подскажите пожалуйста, вот есть рабочий код, но разобраться, что-то совсем не...

Слишком долго отключается компьютер
слишком долго отключается компьютер


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru