IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Проверка числа на простоту, метод Миллера
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Существует ли алгоритм проверки числа на простоту? Я слышала, что можно отличить простое число от составного с помощью метода Миллера. В чем он заключается?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Фанат Delphi
**

Группа: Пользователи
Сообщений: 72
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


Простое число - число, которое имеет только 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)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Профи
****

Группа: Пользователи
Сообщений: 559
Пол: Мужской
Реальное имя: Бруно

Репутация: -  10  +


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


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 47
Пол: Мужской
Реальное имя: Юрий

Репутация: -  0  +


Нет необходимости проверять все делители(от 1 до n).Согласно теореме, если делитель числа не будет найден в пределах от 2 до sqrt(n), то число простое.Метод Миллера я, если честно,что-то забыл blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Свидетели простоты и теорема Рабина
Пусть 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. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости обобщённой гипотезы Римана, но является вероятностным.

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Фанат Delphi
**

Группа: Пользователи
Сообщений: 72
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


Цитата(WishMaster @ 18.03.2007 18:47) *

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

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


--------------------
ICQ (384-043-857)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Цитата(Tan @ 18.03.2007 22:14) *

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

Прошу прощения, я вовсе запоздал, но простые числа нельзя задать данной формулой.
Просто решил внести ясности, дабы не вводить в заблуждение людей, которые возможно будут искать ответ на данный вопрос так же в 2016 году

 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Цитата(Tan @ 18.03.2007 22:14) *

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

Простое число, это число которое делится только на себя и на один, а вы записали просто непарное число
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 21.09.2017 17:30
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"