Developing.ru

Medved писал(а):Не знаю, разве что если русскоязычный форум- это англоязычные ресурсы...

Там идут ссылки на описание методов определения простоты чисел на английских сайтах...

Имеет смысл составить список всех простых чисел до 2^31 (Longint) а потом каждое из 30 млн. проверять на вхождение

По-моему, я читал в книжках, нужно составить список не до 2147483648, а до корня из этого числа, т.е. до 46341 - скорее всего это утверждение верно. Собственно, это я и делаю. Получается массив из 4794 простых чисел.
Потом каждое сгенерированное новое число я проверяю на простоту. Т.е. смотрю делится ли это число на какое-нибудь число из созданного массива. Но в этот то и есть фишка. Получается, что это медленно работает.

WarMaster, я правильно понял, что количество чисел будет порядка 30 млн??
тогда затраты на проверку будут СОПОСТАВИМЫ с нахождением всех простых чисел от 1 до 30 млн. (разумеется не такие же, но хоть оценить время работы алгоритма можно попытаться ;-)))

Да, чисел будет генерироваться чуть более 30 млн.

&quot писал(а):Получается массив из 4794 простых чисел.

Но по размеру они до 2^31

Medved писал(а):Но по размеру они до 2^31

Нет, эти простые числа не превосходят 46341... Этого достаточно.

WarMaster, так нахрена вообще этот массив из 4794 простых нужен, если тебе потом каждое число придется заново проверять на делимость. Я даже щас на вкидку могу сказать что в 25 секунд ты точно не войдешь. Смысл таков что тебе нужно узнать очень быстро - простое число или нет до 2^31. Вот тебе попалось число 278457341 - как ты БЫСТРО узнаешь простое оно или нет, имея список из 4794 простых чисел, в которых все они меньше заданного. Да, ты скажешь: вот я начну проверять делиться ли оно на число из того списка, потому что необходимо и достаточно.... и бла-бла-бла.... это все понятно...а теперь пока ты будешь проверять умножь это время на 300000000 и сразу получаем ответ - в 25 секунд не войдем

somewhere писал(а):WarMaster, так нахрена вообще этот массив из 4794 простых нужен, если тебе потом каждое число придется заново проверять на делимость. Я даже щас на вкидку могу сказать что в 25 секунд ты точно не войдешь. Смысл таков что тебе нужно узнать очень быстро - простое число или нет до 2^31. Вот тебе попалось число 278457341 - как ты БЫСТРО узнаешь простое оно или нет, имея список из 4794 простых чисел, в которых все они меньше заданного. Да, ты скажешь: вот я начну проверять делиться ли оно на число из того списка, потому что необходимо и достаточно.... и бла-бла-бла.... это все понятно...а теперь пока ты будешь проверять умножь это время на 300000000 и сразу получаем ответ - в 25 секунд не войдем

Вы что-нибудь можете предложить другое? Массив простых чисел нужен для ускорения проверки на простоту...

Поскольк каждое из 30 млн. являлется LongInt'ом, то массив и будет самой проверкой. Вам достаточно поискать нужное число в этом массиве. Если нашли, то простое. Поверьте, другими способами проверять 30 млн. чисел очень долго

Полностью согласен с somewhere. Повторю, Боюсь это ЕДИНСТВЕННОЕ решение!

Другой вопрос, что если есть массив с нужными простыми числами, то может генерить их и проверять смысла уже и нет? %-)

И, кстати, WarMaster, позвольте поинтересоваться - а откуда возникла такая задача - особенно интересно ограничение по времени и количество проверяемых чисел?!!

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