0 / 0 / 0
Регистрация: 16.10.2010
Сообщений: 11
|
||||||
1 | ||||||
Поиск простых чисел выполняется слишком долго01.07.2014, 18:09. Показов 2673. Ответов 10
Метки нет (Все метки)
Добрый день,
На Лурке в статье Python (http://lurkmore.to/Python) Приводится код скрипта - поиск простых чисел от 1 до 1 000 0000 и запись найденных в файлик Выполнение данного скрипта у меня заняло 5 минут с гаком. Скажите, пожалуйста, ведь это очень долго, я правильно понимаю? Еще у них есть приписка: "Шах и мат" Есть у кого какие мысли на этот счет? Что они имели в виду? Код привожу ниже.
0
|
01.07.2014, 18:09 | |
Ответы с готовыми решениями:
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 |
деленеие выполняется несколько дольше в машинной арифметике, нежели умножение. А уж проверка делением на большое количество различных чисел ещё более ресурсоёмко. У вас весьма странные представления.
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
02.07.2014, 06:30 | 7 |
При условии, что считали умножением в цикле, сложность O(n). В коде из первого поста грубо говоря (совсем грубо) верхняя оценка будет O(n^2).
0
|
02.07.2014, 07:39 | 8 |
Ну видно же, что для каждого i прога запускает большой цикл. Проверяется каждое число отдельно. Ещё бы оно быстро работало.
Решето Эратосфена - это совсем не то, оно предназначено для отсеивания простых на большом участке.
0
|
117 / 101 / 53
Регистрация: 13.04.2014
Сообщений: 233
|
|||||||||||
02.07.2014, 15:27 | 9 | ||||||||||
Я бы заменил:
на
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 | |
06.07.2014, 01:04 | |
Помогаю со студенческими работами здесь
11
Слишком долго выполняется задача "ка-тая банка" Сумма всех простых чисел меньше двух миллионов - очень долго вычисляется Поиск всех простых чисел в интервале чисел, разделенном на несколько диапазонов Поиск простых чисел среди чисел Фибоначчи с использованием событий Слишком долго отключается компьютер Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |