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

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

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

Вопросы:
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++

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

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

Не по теме:

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

@Retyrn0 45 / 48 / 5 Регистрация: 24.06.2013 Сообщений: 677
	21.07.2013, 19:01	23
	Сообщение от Kuzia domovenok я уверен, имелись в виду числа до 100 возможно имелось ввиду, но фразы "меньше 100" я не нашёл... Сообщение от lazybiz ссылку я нашел, а где там такое сказано - нет ну как же? Листаете до пункта "Некоторые свойства", там 11 по счёту свойство =) Добавлено через 1 минуту Сообщение от aram_gyumri это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое Я осознал свою ошибку, прошу прощения) 1

ValeryS Модератор 8909 / 6678 / 918 Регистрация: 14.02.2011 Сообщений: 23,523
	21.07.2013, 19:12	25
	Сообщение от salam if(n & 1 == 0) return false; число 2 покажет как не простое добавить бы надо 0

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	21.07.2013, 20:53	26
	Сообщение от Kuzia domovenok Тут логическая игра слов с толку немного сбивает. учи матеметику кузя, это некакая не игра слов 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	22.07.2013, 05:34	28
	Сообщение от Retyrn0 Пардоньте, я знал, что википедии доверять нельзя не надо, пожалуйста, обвинять Википедию в ваших логических ошибках. 0

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

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	21.07.2013, 18:41	21
	Сообщение от Retyrn0 Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c) 101 я уверен, имелись в виду числа до 100 0

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	21.07.2013, 18:42	22
	Сообщение от Retyrn0 Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c) это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое 2

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	21.07.2013, 19:02	24
	Сообщение от Retyrn0 возможно имелось ввиду, но фразы "меньше 100" я не нашёл... не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	21.07.2013, 20:59	27
	Сообщение от ALEXKIRNAS Нужно чтобы алгоритм был быстрым Быстрая проверка натурального числа на простоту 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 10:08	31
	вероятностные алгоритмы не всегда хороши. А вообще, можно обобщить. Загадываете произвольное достаточно большое натуральное случайное число меньшее 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	32
	Thinker, да но я не говорил что он на всех числах правильно работает но до 2⁶⁴ все правильно делает Добавлено через 47 секунд и еще откуда такая вероятность? Добавлено через 2 минуты есть и более надежный недетерминированный тест BPSW 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 10:24	33
	Сообщение от aram_gyumri откуда такая вероятность? распределение простых чисел 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.07.2013, 12:54	34
	Сообщение от Thinker а я без проверки буду говорить, что оно не является простым Только ваш алгоритм не сходится. В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается. Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 13:13	35
	Сообщение от diagon Только ваш алгоритм не сходится. В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается. ну, это и так понятно, что в некоторых вероятностных алгоритмах вероятность зависит от некоторых параметров. Сообщение от diagon Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же. видите, не доказано, значит это гипотеза, проверенная на конечном наборе чисел, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться. а вообще, алгоритм получился со сложностью O(1), весело же 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	22.07.2013, 13:17	36
	Сообщение от Thinker а натуральных чисел бесконечно В компьютере конечно. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 13:21	37
	Сообщение от Kuzia domovenok В компьютере конечно. неужели?! так как (при использовании длинной арифметики и росте вычислительных возможностей) нет жесткого ограничения на диапазон рассматриваемых чисел, то замечание совсем не актуально. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.07.2013, 13:22	38
	Сообщение от Thinker видите, не доказано, значит это гипотеза, проверенная на конечном наборе числах, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться. Она доказана, но зависит от этой штуки. А эта штука, между прочим, является проблемой тысячелетия, и за ее доказательство/опровержение дают 1000000$. Т.е. если тест Миллера внезапно не сработает на каком-то числе, то это означает, что для этого числа не работает гипотеза Римана. А это значит, что вы можете получить 1000000$ (так как контрпример является опровержением). 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	22.07.2013, 13:24	39
	Сообщение от diagon Она доказана, но зависит от этой штуки. Не по теме: нельзя говорить, что какое-то утверждение доказано, если оно ссылается на недоказанное утверждение. 0