Простое число

← →
Separator © (2002-12-12 08:16) [0]

Есть ли метод определения простого числа, кроме стандартного перебора

← →
Separator © (2002-12-12 08:46) [1]

Спасибо всем, уже сам решил. Использовал тест простоты Рабина

← →
Uncle Archi © (2002-12-12 12:03) [2]

А что за тест, может расскажешь?

← →
yaJohn © (2002-12-12 12:07) [3]

По слухам, утвердительным ответом на этот вопрос распологают ребята из ЦРУ. Может им написать?

← →
KSergey © (2002-12-12 12:12) [4]

Если я правильно понимаю проблему, утвердительно ответ на этот вопрос не знает никто. Правда, группа индийцев (недавно было в потрепаться на этом форуме) утверждают, что они знают, но народ в сомнении... ;)

← →
Separator © (2002-12-13 10:21) [5]

Ответ на это вопрос можно найти на http://algolist.manual.ru/maths/teornum/rabmil.php

← →
Гарик (2002-12-13 10:50) [6]

По-моему, для этого подойдет так-называемое "Решето Эратосфена".
Оно находит все простые числа в промежутке.

← →
Separator © (2002-12-13 10:54) [7]

А где про это можно почитать?

← →
Гарик (2002-12-13 11:10) [8]

можно здесь:
http://www.yandex.ru/yandsearch?text=%F0%E5%F8%E5%F2%EE+%DD%F0%E0%F2%EE%F1%F4%E5%ED%E0

Решето не подходит.

http://delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1039632745&n=3

Является ли число простым.

Манидра Агравал, Неерай Каял и Нитин Саксена.

Отдел компьютерных и инженерных исседований,
Индийский институт технологий,
Канпур, ИНДИЯ, август 2002.

Мы предоставляем вашему вниманию детерминированный алгоритм определения, является ли число n простым за полиномиальное время.

... (три страницы формул) ...

4. Алгоритм.

1. if (n is of the form a^b, b>1) output COMPOSITE; 2. r=2; 3. while(r<n) { 4. if(gcd(n,r)<>1) output COMPOSITE; 5. if(r is prime) 6. let q be the largest prime factor of r - 1 7. if (q>=4*sqrt(r)*ln(n)) and (N^((r-1)/q) не сравнимо с единицей по модулю r)) 8. break; 9. r := r + 1; 10. } 11. for a=1 to 2*sqrt(r)*ln(n) 12. if((x-a)^n не сравнимо с (x^n-a) по модулю x^r-1, n) output COMPOSITE; 13. output PRIME;

Теоремы, доказывающие правильность работы алгоритма, оценка времени выполнения, ... (еще 5 страниц) + страница библографии

Могу выслать (PDF, 195 Кб), только там все на ангельском. Писать на мыло.

Простое число Найти похожие ветки