Поиск простых чисел в заданом диапозоне
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Поиск простых чисел в заданом диапозоне - 2010-03-07 17:12:01.170000
|
|
|
нетумнутута
Сообщений: 6
Оценки: 0
Присоединился: 2010-01-10 13:49:22.986666
|
Необходимо найти простые числа в диапозоне 0-1299710 (100000 штук должно быть) за минимальное время. Реализуется на AutoIt.
Пробовал перебирать:
Каждое нечётное число делится на уже найденные простые числа, которые меньше корня проверяемого числа. Если результат - целое число, проверяемое число не является простым.
В принципе работает, но длится полторы с лишним минуты. У пишущих аналогичную фигню людей результаты около 5 секунд.
Может кто-нибудь алгоритм по бысрее подскажет?
(Поиск не рулит - руль кривой)
|
|
|
|
|
RE: Поиск простых чисел в заданом диапозоне - 2010-03-07 23:18:02.063333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Что-то мне подсказывает, что если у других это занимает всего 5 секунд, а у тебя аж 1.5 минуты, то это просто недочёт в коде, поэтому для начала перепроверь ка всё.
Если с кодом всё ок, то можешь для проверки "простоты" числа использовать тест Ферма (только не забудь потом выбросить из результатов кармайкловы числа), или попробовать реализовать AKS. По идее, AKS будет лучше, но если честно, сам его никогда не разбирал и не реализовал, поэтому не исключаю, что где-то может быть подстава.
|
|
|
|
|
RE: Поиск простых чисел в заданом диапозоне - 2010-03-08 17:21:47.293333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
http://cr.yp.to/primegen.html
|
|
|
|
|
|
