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

@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

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

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@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