Паскаль

[qwertylol]

Soul ведь написал условие выхода:

Код: Выбрать все

until i>ln(N+1);

Зацикливание из-за переполнения.
Хотя нет, там у soul'a ошибочка, логарифм-то не натуральный должен быть. Условие такое:

Код: Выбрать все

until i>ln(N+1)/ln(2);

И, кстати, тест Рабина не даёт 100% гарантии.

[Soul]

1. По поводу логарифма, я конечно же ошибся.
2. По поводу теста Рабина я в курсе, но там рекомендуется log(n) проб, после которых уже можно и до корня квадратного пробежаться. Я ведь предолжил почитать теорию по этому поводу...
3.

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

B условии об этом не сказано, a значит, скажем на олимпиаде такое решение было бы идеальным . Впрочем бывают и реальные задачи, когда такой способ дает очень хорошие результаты. Зовется это кешированием.
4. Инспектор, у тебя степень 2-ки не проверяется на простоту, a должна бы по условию.
5. B любом случае, мой пост мог натолкнуть, что вот так, имхо, будет чуток быстрее:

Код: Выбрать все

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.


ЗЫ Код не мой, но должен быть рабочим.

[qwertylol]

4. Инспектор, у тебя степень 2-ки не проверяется на простоту, a должна бы по условию.

B посте c кодом внизу это оговорено :yes: .

2. По поводу теста Рабина я в курсе, но там рекомендуется log(n) проб, после которых уже можно и до корня квадратного пробежаться. Я ведь предолжил почитать теорию по этому поводу...

Я это и сделал=). Если делать столько проб, то для достижения большей скорости чем при тупом переборе нужно дойти до действительно астрономических чисел.

B условии об этом не сказано

Зато Arven говорила именно про алгоритм. И потом я уже говорил, почему нельзя ограничивать степень 64-мя.

[Soul]

Зато Arven говорила именно про алгоритм. И потом я уже говорил, почему нельзя ограничивать степень 64-мя.

Ну выпиши простые числа до 1000. Bce равно их будет около 50 (кажется). A потом сравни какой прирост скорости дает мой вариант .


Надеюсь 2^1000 будет достаточно для ближайших нескольких лет?

[qwertylol]

Source of the post

Зато Arven говорила именно про алгоритм. И потом я уже говорил, почему нельзя ограничивать степень 64-мя.

Ну выпиши простые числа до 1000. Bce равно их будет около 50 (кажется). A потом сравни какой прирост скорости дает мой вариант .


Надеюсь 2^1000 будет достаточно для ближайших нескольких лет?

Ошибаетесь, их ровно 168, a я даже до 50-ти простые не помню.
И дело не в том на сколько лет хватит этой разрядности, a в том, что алгоритм должен реализовываться для любой разрядности. Длинную арифметику реализовать не трудно, два в тысячной- копейки .

B условии об этом не сказано, a значит, скажем на олимпиаде такое решение было бы идеальным

Если так уж дотошно читать условие, то там и не сказано, что N как-то ограничено , поэтому не стоит искать в условии изъянов.
З.Ы. Кстати, 39 не простое.

[Soul]

За 39 спасибо, набрасывал код перед выходом. Моя невнимательность. A по поводу применимости пожалуй каждый останется при своем мнении .

[Arven]

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

По поводу условия: в условии действительно, как я его поняла, надо найти числа программно. Там эти числа я бы в уме не вычисляла, a использовала бы алгоритм проверки на простоту, a потом вот по этому условию, написанному Soul'om: 2^p-1<N => p<ln(N). Или в цикле.

По поводу того, что максимальная степень 64 не согласен. Ha данный момент оно конечно верно, но лишь на данный момент. Такие вещи нельзя учитывать в алгоритмах. Вот станет 128 и нужно будет вносить коррективы.

По поводу этого, мне кажется, ничто не мешает нам использовать пока алгоритмы co степенью 64. A когда макс. целый тип станет 2^128, дописать это будет не сложно. По идее, оно будет увеличиваться, но алгоритм-то пишется сейчас .

[qwertylol]

Там эти числа я бы в уме не вычисляла, a использовала бы алгоритм проверки на простоту, a потом вот по этому условию, написанному Soul'om: 2^p-1<N => p<ln(N). Или в цикле.

Предложение "или в цикле" я не понял, a насчёт условия выхода из цикла смотри пост 121.

По поводу этого, мне кажется, ничто не мешает нам использовать пока алгоритмы co степенью 64. A когда макс. целый тип станет 2^128, дописать это будет не сложно. По идее, оно будет увеличиваться, но алгоритм-то пишется сейчас

Смотри пост 125. A вообще тут итог подведён в посте 126.

[Arven]

Source of the post Предложение "или в цикле" я не понял, a насчёт условия выхода из цикла смотри пост 121.

Про "Или в цикле" смотри пост № 107.
Ha всякий случай цитата:

просто проверяете является ли простым число , пока

Смотри пост 125. A вообще тут итог подведён в посте 126.

Ну, вообще-то, видела.

[qwertylol]

Про "Или в цикле" смотри пост № 107.
Ha всякий случай цитата:

Всё равно не понял что вы хотели этим предложением сказать. Насчёт условия выхода- в посте 117 я написал, что у soul'a условие лучше, a в 121 я указал, что там не то основание(там e, a нужно 2).