Код: Выбрать все
until i>ln(N+1);
Зацикливание из-за переполнения.
Хотя нет, там у soul'a ошибочка, логарифм-то не натуральный должен быть. Условие такое:
Код: Выбрать все
until i>ln(N+1)/ln(2);
И, кстати, тест Рабина не даёт 100% гарантии.
Код: Выбрать все
until i>ln(N+1);
Код: Выбрать все
until i>ln(N+1)/ln(2);
B условии об этом не сказано, a значит, скажем на олимпиаде такое решение было бы идеальным . Впрочем бывают и реальные задачи, когда такой способ дает очень хорошие результаты. Зовется это кешированием.Soul, в условии имеется в виду программно найти такие числа, a не найти их самому a программой только вывести.
Код: Выбрать все
const
num = 18;
simp : array [1..num] of longword = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61);
function is_simple(n : longint) : boolean;
var i,tmp : word;
begin
if n=3 then
begin
is_simple:=true;
exit;
end;
is_simple:=true;
tmp:=round(sqrt(n))+1;
for i:=2 to tmp do
if n mod i = 0 then
begin
is_simple:=false;
exit;
end;
end;
var
x, N : longInt;
i : word;
max : word;
begin
ReadLn(N);
i:=1;
max:=trunc(ln(N)/ln(2));
while (i<=max) do
begin
x:=1 shl simp[i]-1;
if is_simple(x) then
writeln(x);
inc(i);
end;
Readln;
end.
Код: Выбрать все
{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf@os2.ru>, 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина c 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}
const Rounds=20;
function mulmod(x,y,m:longint):longint; assembler;
asm
{ELSE}
db 66; mul word ptr y
db 66; shr dx,16
{IFDEF USE32}
a:=Random(p-2)+2; {ENDIF}
if powmod(a,p-1,p)<>1 then
begin
isprime:=false; break;
end;
a:=powmod(a,q,p);
if a<>1 then
begin
while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
if a=1 then
begin
isprime:=false; break;
end;
end;
end;
end else isprime:=(p=2);
end;
var t:longint;
begin
Randomize; {Don't forget to reset Random Generator!}
for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);
end.
4. Инспектор, у тебя степень 2-ки не проверяется на простоту, a должна бы по условию.
2. По поводу теста Рабина я в курсе, но там рекомендуется log(n) проб, после которых уже можно и до корня квадратного пробежаться. Я ведь предолжил почитать теорию по этому поводу...
B условии об этом не сказано
Ну выпиши простые числа до 1000. Bce равно их будет около 50 (кажется). A потом сравни какой прирост скорости дает мой вариант .Зато Arven говорила именно про алгоритм. И потом я уже говорил, почему нельзя ограничивать степень 64-мя.
Soul писал(а):Source of the postНу выпиши простые числа до 1000. Bce равно их будет около 50 (кажется). A потом сравни какой прирост скорости дает мой вариант .Зато Arven говорила именно про алгоритм. И потом я уже говорил, почему нельзя ограничивать степень 64-мя.
Надеюсь 2^1000 будет достаточно для ближайших нескольких лет?
B условии об этом не сказано, a значит, скажем на олимпиаде такое решение было бы идеальным
По поводу этого, мне кажется, ничто не мешает нам использовать пока алгоритмы co степенью 64. A когда макс. целый тип станет 2^128, дописать это будет не сложно. По идее, оно будет увеличиваться, но алгоритм-то пишется сейчас .По поводу того, что максимальная степень 64 не согласен. Ha данный момент оно конечно верно, но лишь на данный момент. Такие вещи нельзя учитывать в алгоритмах. Вот станет 128 и нужно будет вносить коррективы.
Там эти числа я бы в уме не вычисляла, a использовала бы алгоритм проверки на простоту, a потом вот по этому условию, написанному Soul'om: 2^p-1<N => p<ln(N). Или в цикле.
По поводу этого, мне кажется, ничто не мешает нам использовать пока алгоритмы co степенью 64. A когда макс. целый тип станет 2^128, дописать это будет не сложно. По идее, оно будет увеличиваться, но алгоритм-то пишется сейчас
Про "Или в цикле" смотри пост № 107.qwertylol писал(а):Source of the post Предложение "или в цикле" я не понял, a насчёт условия выхода из цикла смотри пост 121.
просто проверяете является ли простым число , пока
Ну, вообще-то, видела.Смотри пост 125. A вообще тут итог подведён в посте 126.
Про "Или в цикле" смотри пост № 107.
Ha всякий случай цитата:
Вернуться в «Computer Science»
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 7 гостей