Форум: "Основная";
Текущий архив: 2002.12.23;
Скачать: [xml.tar.bz2];
ВнизПростое число Найти похожие ветки
← →
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
← →
Uncle Archi (2002-12-13 21:46) [9]Решето не подходит.
← →
LongIsland (2002-12-13 22:01) [10]http://delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1039632745&n=3
← →
Mystic (2002-12-14 05:20) [11]Является ли число простым.
Манидра Агравал, Неерай Каял и Нитин Саксена.
Отдел компьютерных и инженерных исседований,
Индийский институт технологий,
Канпур, ИНДИЯ, август 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 Кб), только там все на ангельском. Писать на мыло.
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2002.12.23;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.459 c