Буду рад любой помощи - как решениям на Паскале, так и советам...
Каким-то образом по некоторой формуле (если вам интересно, то могу и рассказать конкретней) генерируются числа. По моей предварительной оценке числа эти получаются в пределах типа longint. Чисел этих около 30 млн надо сгенерировать. И всех их проверить на простоту. Времени дается 25 секунд.
Можете дать какие-нибудь советы по реализации?
Задача о простых числах
Модераторы: Хыиуду, MOTOCoder, Medved, dr.Jekill
Есть такой алгоритм, но он похоже слишком медленный.
[syntax='Delphi']
var
j,k,i:longint;
const
N=30000000;
begin
while I< N do
begin
J:=2;
K:=I div 2;
while (I mod J <> 0) and (J < K) do inc(J);
If J=K then
writeln (I);
i:=i+1;
end;
readln;
end.
[/syntax]
[syntax='Delphi']
var
j,k,i:longint;
const
N=30000000;
begin
while I< N do
begin
J:=2;
K:=I div 2;
while (I mod J <> 0) and (J < K) do inc(J);
If J=K then
writeln (I);
i:=i+1;
end;
readln;
end.
[/syntax]
Ни что так не ограничивает фантазию программиста, как компилятор...
-
Serge_Bliznykov
- Сообщения: 375
- Зарегистрирован: 31 авг 2007, 03:06
ошибся... стёр всё.
посмотрите вот сюда - http://forum.vingrad.ru/forum/topic-29008.html
или
сюда - http://irodov.nm.ru/cgi-bin/ikonboard/t ... &topic=846
посмотрите вот сюда - http://forum.vingrad.ru/forum/topic-29008.html
или
сюда - http://irodov.nm.ru/cgi-bin/ikonboard/t ... &topic=846
MOTOcoder, алгоритм медленный, да и еще не соответствует условию задачи.
Не надо находить все простые числа от нуля до 30 млн.
Фишка в том, что первое число - это 1, а каждое следующее генерируется рекуррентным уравнением (соотношением). Вот при каждой новой генерации и нужно определить является ли новое сгенерированное число простым или нет...
Не надо находить все простые числа от нуля до 30 млн.
Фишка в том, что первое число - это 1, а каждое следующее генерируется рекуррентным уравнением (соотношением). Вот при каждой новой генерации и нужно определить является ли новое сгенерированное число простым или нет...
Serge_Bliznykov, не совсем понял, что же делает этот алгоритм... Поясните, пожалуйста...
По этим ссылкам я нашел еще одни ссылки на англоязычные ресурсы. Вообще подобную информацию я нашел в wikipedia. Слов там много, а дела мало... Мне бы листинг самого решения НА ПАСКАЛЕ самого быстрого (или как можно быстрого) определения того, является ли вводимое число простым или составным.Serge_Bliznykov писал(а):ошибся... стёр всё.
посмотрите вот сюда - http://forum.vingrad.ru/forum/topic-29008.html
или
сюда - http://irodov.nm.ru/cgi-bin/ikonboard/t ... &topic=846
Не знаю, разве что если русскоязычный форум- это англоязычные ресурсы..." писал(а):По этим ссылкам я нашел еще одни ссылки на англоязычные ресурсы
Ваши руки совершили идиотскую ошибку и будут оторваны!
[OK]
[OK]
Имеет смысл составить список всех простых чисел до 2^31 (Longint) а потом каждое из 30 млн. проверять на вхождение
It's a long way to the top if you wanna rock'n'roll
+1!" писал(а):Имеет смысл составить список всех простых чисел до 2^31 (Longint) а потом каждое из 30 млн. проверять на вхождение
Константный массив - метод века! Мгновенно работает!
Ваши руки совершили идиотскую ошибку и будут оторваны!
[OK]
[OK]
-
Serge_Bliznykov
- Сообщения: 375
- Зарегистрирован: 31 авг 2007, 03:06
WarMaster, я правильно понял, что количество чисел будет порядка 30 млн??
тогда затраты на проверку будут СОПОСТАВИМЫ с нахождением всех простых чисел от 1 до 30 млн. (разумеется не такие же, но хоть оценить время работы алгоритма можно попытаться ;-)))
Более того, я практически уверен, что это единственное решение, которое пройдёт в рамки ограничения скорости...
тогда затраты на проверку будут СОПОСТАВИМЫ с нахождением всех простых чисел от 1 до 30 млн. (разумеется не такие же, но хоть оценить время работы алгоритма можно попытаться ;-)))
+1" писал(а):Имеет смысл составить список всех простых чисел до 2^31 (Longint) а потом каждое из 30 млн. проверять на вхождение
Более того, я практически уверен, что это единственное решение, которое пройдёт в рамки ограничения скорости...