Поиск простых чисел

[Sonic86]

bot в сообщении #518471 писал(а):

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

Не совсем так. Важен аспект скорости работы. И потому алгоритм, вычисляющий сразу кучу подряд идущих простых чисел в заданных пределах, часто не медленнее и даже быстрее, чем алгоритм, считающий числа по одному. Если он, конечно, нужен. А он бывает нужен.

[Someone]

Если речь идёт о нахождении всех простых чисел в заданном промежутке, то, вроде бы, такие программы есть: http://primes.utm.edu/links/programs/sieves/. И работают они быстро.

[ananova]

magistr07
Действительно, новость свежая! Надо найти подробности, а то слышу звон, но не знаю где он.

[dmd]

Аналоги простых Мерсенна.

Пусть $n$ - любое натуральное не степень двойки, $p$ - простое $>3$, и $T=\frac{2^p+1}{3}$.

Тогда $T$ будет простым если выполняется сравнение

$n^\frac{T-1}{2p}\equiv -2^x\pmod T$

где $x$ - некое натуральное $<p$

Наверняка есть исключения, но у меня не получилось найти ни одного.

tst()=
{
forprime(p=5, 2000,
 T= (2^p+1)/3;
 s= (T-1)/2/p;
 r= lift(-Mod(3,T)^s);
 if(r==2^valuation(r,2),
  print(p,"    ",isprime(T))
 )
)
};

[maxal]

dmd в сообщении #519718 писал(а):

Пусть $n$ - любое натуральное не степень двойки, $p$ - простое $>3$, и $T=\frac{2^p+1}{3}$.

Тогда $T$ будет простым если

Такие простые называются простыми Вагстафа (Wagstaff primes). Их известно не так много - см. A000978.

А ваш код пропускает, например, $p=11$ и $p=13$.

[dmd]

(Оффтоп)

Случайный это выброс или нет?

Пусть $p$ - простое и $t$ - период квадратичной иррациональности $\sqrt p$
$M=2^p-1$ либо $M=(2^p+1)/3$

Тогда если $p+1|M-1$, то возможно и $t|M-1$

\p 10000
pki()=
{
forprime(p=2, 10000,
 M= 2^p-1;
\\ M= (2^p+1)/3;
 u=contfrac(sqrt(p));
 for(j=2,#u, if(u[j]==2*u[1], t= j-1; break()));
 if(t>1,
  m= (M-1)%(p+1); n= (M-1)%t;
  if(m==0, if(n==0, print(p,"    ",t)))
 )
)
};

[maxal]

dmd в сообщении #521697 писал(а):

Пусть $p$ - простое и $t$ - период квадратичной иррациональности $\sqrt p$
$M=2^p-1$ либо $M=(2^p+1)/3$

Тогда если $p+1|M-1$, то возможно и $t|M-1$

Вы как-то странно тестируете. Например, для $p=157$ и $M=2^p-1$ делимость $(p+1)|(M-1)$ есть, а делимости $t|(M-1)$ нет.

[dmd]

Еще одно условие для простых Мерсенна: отрицательная нечетная степень тройки должна быть квадратичным вычетом по модулю $M$

$x^2\equiv -3^y\pmod M$

где $x$ - натуральное не степень двойки
$y$ - нечетное натуральное
$M=2^p-1$
$p$ - искомое простое

tst()=
{
forprime(p=2, 4000,
 M= 2^p-1;
 t= trap(, 0, sqrt(O(M) - 3));
 if(t, print(p))
)
};

[maxal]

dmd в сообщении #522332 писал(а):

Еще одно условие для простых Мерсенна: отрицательная нечетная степень тройки должна быть квадратичным вычетом по модулю $M$

Для простых чисел Мерсенна это простое следствие квадратичного закона взаимности. А для составных чисел Мерсенна это утверждение неверно.

[Sonic86]

Кто-нибудь знает, исследовалась ли простота чисел вида $3^n-2^n$? Что-то я ничего нагуглить не могу. Может они как-то называются?
В OEIS есть последовательность A058765, но там ссылок нет.

[maxal]

Sonic86 в сообщении #526880 писал(а):

Кто-нибудь знает, исследовалась ли простота чисел вида $3^n-2^n$? Что-то я ничего нагуглить не могу. Может они как-то называются?
В OEIS есть последовательность A058765, но там ссылок нет.

Ссылки есть в A057468.

[Sonic86]

maxal в сообщении #527010 писал(а):

Ссылки есть в A057468.

Оо! Спасибо!
Я не додумался искать по показателям.
Но теста простоты у них там нет. Ну и ладно...

[Kover]

Решето Сундарама отсеивает 67 228 644 простых чисел из 671 000 000 нечетных чисел за 9 сек на обычном ПК. Это в четыре раза (!) быстрее Аткина-Бернстейна. Только это решето надо правильно реализовать. Весьма забавно выглядит замечание о том, что "Си гораздо бастрее Паскаля". Видимо, "в попугаях оно гораздо длиннее!"

[venco]

Kover в сообщении #536704 писал(а):

Решето Сундарама отсеивает 67 228 644 простых чисел из 671 000 000 нечетных чисел за 9 сек на обычном ПК. Это в четыре раза (!) быстрее Аткина-Бернстейна. Только это решето надо правильно реализовать.

Надо ещё решето Аткина "правильно" реализовать.
Кстати, решето Эратосфена отсеивает 67 228 644 простых чисел из 671 000 000 нечетных чисел за 1.3 сек на обычном ПК.

[yk2ru]

У всех ПК разные. Где одно ядро, а где и более, да частоты разные у процессоров.