Проверка числа на простоту, метод Миллера Опции

[Тёмный Эльф]

Существует ли алгоритм проверки числа на простоту? Я слышала, что можно отличить простое число от составного с помощью метода Миллера. В чем он заключается?

[NTL]

Простое число - число, которое имеет только 2 делителя:само себя и единицу.

Код

k:=0;
for i:=1 to n do{n - число для проверки на простоту}
       if n mod i=0 then inc(k);

if k=2 then write(k,' - simple')
else write(k,' - not simple')

[Tan]

Немного непонятна глубина вопроса, простое число это число которое можно задать выражение 2n + 1, где n принадлежит множество целых чисел. Тебе требуется какой - то теоретический алгоритм или код ?

[WishMaster]

Нет необходимости проверять все делители(от 1 до n).Согласно теореме, если делитель числа не будет найден в пределах от 2 до sqrt(n), то число простое.Метод Миллера я, если честно,что-то забыл

[Тёмный Эльф]

Свидетели простоты и теорема Рабина
Пусть m — нечётное число большее 1. Число m - 1 однозначно представляется в виде , где t нечётно. Целое число a, 1 < a < m, называется свидетелем простоты числа m, если выполняются два условия:

m не делится на a;
или существует целое k, , такое, что
Теорема Рабина утверждает, что составное нечётное число m имеет не более различных свидетелей простоты, где — функция Эйлера.


Алгоритм Миллера — Рабина
Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины log2(m), где m — проверяемое число.

Для данного m находятся такие целое число s и целое нечётное число t, что m − 1 = 2st. Выбирается случайное число a,1 < a < m. Если a не является свидетелем простоты числа m, то выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм завершается.

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того, что m составное, не превосходит 4 - r.


Алгоритм Миллера
Изначальный алгоритм, предложенный Миллером, был детерминированным и состоял в проверке всех a от 2 до 70ln(m)2. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости обобщённой гипотезы Римана, но является вероятностным.

(информация взята с сайта Википедии)

[NTL]

Нет необходимости проверять все делители(от 1 до n)

Нас учили, если вы забыли какую-то теорему, то попробуйте сами ее вывести. Это, как говорится, вариант расчет "в лоб".

[Гость]

program abc;
var n,y: Integer; a: String[9];
begin readln(n); y:= 2; a:='Простое';
While y<=n div y do
If n mod y = 0 then begin a:= 'Составное'; break end
Else y:=y + 1;
Writeln(a);
end.