Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Separator © (2002-12-12 08:16:00)
Есть ли метод определения простого числа, кроме стандартного перебора

Mystic (2002-12-14 05:20:00) [1]
Является ли число простым.

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

Отдел компьютерных и инженерных исседований,
Индийский институт технологий,
Канпур, ИНДИЯ, август 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 Кб), только там все на ангельском. Писать на мыло.

LongIsland (2002-12-13 22:01:00) [2]
http://delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1039632745&n=3

Uncle Archi (2002-12-13 21:46:00) [3]
Решето не подходит.

Гарик (2002-12-13 11:10:00) [4]
можно здесь:
http://www.yandex.ru/yandsearch?text=%F0%E5%F8%E5%F2%EE+%DD%F0%E0%F2%EE%F1%F4%E5%ED%E0

Separator (2002-12-13 10:54:00) [5]
А где про это можно почитать?

Гарик (2002-12-13 10:50:00) [6]
По-моему, для этого подойдет так-называемое "Решето Эратосфена".
Оно находит все простые числа в промежутке.

Separator (2002-12-13 10:21:00) [7]
Ответ на это вопрос можно найти на http://algolist.manual.ru/maths/teornum/rabmil.php

KSergey (2002-12-12 12:12:00) [8]
Если я правильно понимаю проблему, утвердительно ответ на этот вопрос не знает никто. Правда, группа индийцев (недавно было в потрепаться на этом форуме) утверждают, что они знают, но народ в сомнении... ;)

yaJohn (2002-12-12 12:07:00) [9]
По слухам, утвердительным ответом на этот вопрос распологают ребята из ЦРУ. Может им написать?

Uncle Archi (2002-12-12 12:03:00) [10]
А что за тест, может расскажешь?

Separator (2002-12-12 08:46:00) [11]
Спасибо всем, уже сам решил. Использовал тест простоты Рабина

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »