![]() |
1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!
![]() ![]() |
![]() |
Тёмный Эльф |
![]() ![]()
Сообщение
#1
|
![]() Влюблённый псих ![]() ![]() ![]() Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: ![]() ![]() ![]() |
Существует ли алгоритм проверки числа на простоту? Я слышала, что можно отличить простое число от составного с помощью метода Миллера. В чем он заключается?
|
NTL |
![]()
Сообщение
#2
|
![]() Фанат Delphi ![]() ![]() Группа: Пользователи Сообщений: 72 Пол: Мужской Реальное имя: Сергей Репутация: ![]() ![]() ![]() |
Простое число - число, которое имеет только 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') -------------------- ICQ (384-043-857)
|
Tan |
![]()
Сообщение
#3
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 559 Пол: Мужской Реальное имя: Бруно Репутация: ![]() ![]() ![]() |
Немного непонятна глубина вопроса, простое число это число которое можно задать выражение 2n + 1, где n принадлежит множество целых чисел. Тебе требуется какой - то теоретический алгоритм или код ?
-------------------- Цитата Imagination is more important than knowledge. Albert Einstein |
WishMaster |
![]()
Сообщение
#4
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 47 Пол: Мужской Реальное имя: Юрий Репутация: ![]() ![]() ![]() |
Нет необходимости проверять все делители(от 1 до n).Согласно теореме, если делитель числа не будет найден в пределах от 2 до sqrt(n), то число простое.Метод Миллера я, если честно,что-то забыл
![]() |
Тёмный Эльф |
![]()
Сообщение
#5
|
![]() Влюблённый псих ![]() ![]() ![]() Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: ![]() ![]() ![]() |
Свидетели простоты и теорема Рабина
Пусть 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 |
![]()
Сообщение
#6
|
![]() Фанат Delphi ![]() ![]() Группа: Пользователи Сообщений: 72 Пол: Мужской Реальное имя: Сергей Репутация: ![]() ![]() ![]() |
Нет необходимости проверять все делители(от 1 до n) Нас учили, если вы забыли какую-то теорему, то попробуйте сами ее вывести. Это, как говорится, вариант расчет "в лоб". -------------------- ICQ (384-043-857)
|
Гость |
![]()
Сообщение
#7
|
Гость ![]() |
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. |
![]() ![]() |
![]() |
Текстовая версия | 11.09.2024 7:44 |