Алгоритм нахождения простых чисел

@ALEXKIRNAS · Регистрация: 27.06.2013

Студворк — интернет-сервис помощи студентам

Вопросы:
1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 10⁴ операций за 0.5 сек )!!!!
2) Почему мой алгоритм проверки не всегда дает верный ответ?

C++
1
if(x%2 && x%3 && x%5 && x%7) std::cout << "Число простое!\n";

@Kuzia domovenok · 21.07.2013, 18:41

Сообщение от Retyrn0

Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)

101
я уверен, имелись в виду числа до 100

@dr.curse · 21.07.2013, 18:42

Сообщение от Retyrn0

Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)

это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое

@Retyrn0 · 21.07.2013, 19:01

Сообщение от Kuzia domovenok

я уверен, имелись в виду числа до 100

возможно имелось ввиду, но фразы "меньше 100" я не нашёл...

Сообщение от lazybiz

ссылку я нашел, а где там такое сказано - нет

ну как же? Листаете до пункта "Некоторые свойства", там 11 по счёту свойство =)

Добавлено через 1 минуту

Сообщение от aram_gyumri

это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое

Я осознал свою ошибку, прошу прощения)

@Kuzia domovenok · 21.07.2013, 19:02

Сообщение от Retyrn0

возможно имелось ввиду, но фразы "меньше 100" я не нашёл...

не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.

ValeryS · 21.07.2013, 19:12

Сообщение от salam

if(n & 1 == 0) return false;

число 2 покажет как не простое
добавить бы надо

@dr.curse · 21.07.2013, 20:53

Сообщение от Kuzia domovenok

Тут логическая игра слов с толку немного сбивает.

учи матеметику кузя, это некакая не игра слов

@Thinker · 21.07.2013, 20:59

Сообщение от ALEXKIRNAS

Нужно чтобы алгоритм был быстрым

Быстрая проверка натурального числа на простоту

@salam · 22.07.2013, 05:34

Сообщение от Retyrn0

Пардоньте, я знал, что википедии доверять нельзя

не надо, пожалуйста, обвинять Википедию в ваших логических ошибках.

@Thinker · 22.07.2013, 08:34

Сообщение от Kuzia domovenok

C++
1
  if (n==1 || n==2 || n==3) return 1;

Не по теме:

1 - не простое число

Сообщение от OhMyGodSoLong

C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 3; i*i <= n; i += 2)
 
||
\/
 
for (int i = 3, i_sq = 9; i_sq <= n; i_sq += (i + 1) << 2, i += 2)
 
||
\/
 
int n_sqrt = sqrt(n);
for (int i = 3; i <= n_sqrt; i += 2)

такая оптимизация почти не заметна при тестировании чисел, скажем, от 1 до 10 000 000, выигрыш - сотые доли секунды. А вот если уменьшить количество лишних проверок, то можно скорость в разы увеличить.

@dr.curse · 22.07.2013, 09:46

а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log³n), если память не изменяет то была задачка проверки на простоту чисел <2⁶⁴ и решалaсь она миллером-рабином

@Thinker · 22.07.2013, 10:08

вероятностные алгоритмы не всегда хороши. А вообще, можно обобщить. Загадываете произвольное достаточно большое натуральное случайное число меньшее N, а я без проверки буду говорить, что оно не является простым, и с вероятностью
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{ln N - 1}{ln N}$
буду прав. А при росте N эта вероятность стремится к 1.

@dr.curse · 22.07.2013, 10:14

Thinker, да но я не говорил что он на всех числах правильно работает но до 2⁶⁴ все правильно делает

Добавлено через 47 секунд
и еще откуда такая вероятность?

Добавлено через 2 минуты
есть и более надежный недетерминированный тест BPSW

@Thinker · 22.07.2013, 10:24

Сообщение от aram_gyumri

откуда такая вероятность?

распределение простых чисел

@diagon · 22.07.2013, 12:54

Сообщение от Thinker

а я без проверки буду говорить, что оно не является простым

Только ваш алгоритм не сходится.
В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается.
Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же.

@Thinker · 22.07.2013, 13:13

Сообщение от diagon

Только ваш алгоритм не сходится.
В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается.

ну, это и так понятно, что в некоторых вероятностных алгоритмах вероятность зависит от некоторых параметров.

Сообщение от diagon

Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же.

видите, не доказано, значит это гипотеза, проверенная на конечном наборе чисел, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться.

а вообще, алгоритм получился со сложностью O(1), весело же

@Kuzia domovenok · 22.07.2013, 13:17

Сообщение от Thinker

а натуральных чисел бесконечно

В компьютере конечно.

@Thinker · 22.07.2013, 13:21

Сообщение от Kuzia domovenok

В компьютере конечно.

неужели?! так как (при использовании длинной арифметики и росте вычислительных возможностей) нет жесткого ограничения на диапазон рассматриваемых чисел, то замечание совсем не актуально.

@diagon · 22.07.2013, 13:22

Сообщение от Thinker

видите, не доказано, значит это гипотеза, проверенная на конечном наборе числах, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться.

Она доказана, но зависит от этой штуки. А эта штука, между прочим, является проблемой тысячелетия, и за ее доказательство/опровержение дают 1000000$.
Т.е. если тест Миллера внезапно не сработает на каком-то числе, то это означает, что для этого числа не работает гипотеза Римана. А это значит, что вы можете получить 1000000$ (так как контрпример является опровержением).

@Thinker · 22.07.2013, 13:24

Сообщение от diagon

Она доказана, но зависит от этой штуки.

Не по теме:

нельзя говорить, что какое-то утверждение доказано, если оно ссылается на недоказанное утверждение.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	22.07.2013, 09:46
	а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log³n), если память не изменяет то была задачка проверки на простоту чисел <2⁶⁴ и решалaсь она миллером-рабином 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 10:08
	вероятностные алгоритмы не всегда хороши. А вообще, можно обобщить. Загадываете произвольное достаточно большое натуральное случайное число меньшее N, а я без проверки буду говорить, что оно не является простым, и с вероятностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{ln N - 1}{ln N}$ буду прав. А при росте N эта вероятность стремится к 1. 0

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	22.07.2013, 10:14
	Thinker, да но я не говорил что он на всех числах правильно работает но до 2⁶⁴ все правильно делает Добавлено через 47 секунд и еще откуда такая вероятность? Добавлено через 2 минуты есть и более надежный недетерминированный тест BPSW 0