Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
21.07.2013, 16:52     Алгоритм нахождения простых чисел #1
Вопросы:
1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за 0.5 сек )!!!!
2) Почему мой алгоритм проверки не всегда дает верный ответ?

C++
1
if(x%2 && x%3 && x%5 && x%7) std::cout << "Число простое!\n";
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.07.2013, 18:41     Алгоритм нахождения простых чисел #21
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
101
я уверен, имелись в виду числа до 100
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 18:42     Алгоритм нахождения простых чисел #22
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
21.07.2013, 19:01     Алгоритм нахождения простых чисел #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
я уверен, имелись в виду числа до 100
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...

Цитата Сообщение от lazybiz Посмотреть сообщение
ссылку я нашел, а где там такое сказано - нет
ну как же? Листаете до пункта "Некоторые свойства", там 11 по счёту свойство =)

Добавлено через 1 минуту
Цитата Сообщение от aram_gyumri Посмотреть сообщение
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
Я осознал свою ошибку, прошу прощения)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.07.2013, 19:02     Алгоритм нахождения простых чисел #24
Цитата Сообщение от Retyrn0 Посмотреть сообщение
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...
не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.
ValeryS
Модератор
6378 / 4844 / 442
Регистрация: 14.02.2011
Сообщений: 16,066
21.07.2013, 19:12     Алгоритм нахождения простых чисел #25
Цитата Сообщение от salam Посмотреть сообщение
if(n & 1 == 0) return false;
число 2 покажет как не простое
добавить бы надо
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 20:53     Алгоритм нахождения простых чисел #26
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Тут логическая игра слов с толку немного сбивает.
учи матеметику кузя, это некакая не игра слов
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 20:59     Алгоритм нахождения простых чисел #27
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Нужно чтобы алгоритм был быстрым
Быстрая проверка натурального числа на простоту
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
22.07.2013, 05:34     Алгоритм нахождения простых чисел #28
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
не надо, пожалуйста, обвинять Википедию в ваших логических ошибках.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 08:34     Алгоритм нахождения простых чисел #29
Цитата Сообщение от 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
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 09:46     Алгоритм нахождения простых чисел #30
а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log3n), если память не изменяет то была задачка проверки на простоту чисел <264 и решалaсь она миллером-рабином
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 10:08     Алгоритм нахождения простых чисел #31
вероятностные алгоритмы не всегда хороши. А вообще, можно обобщить. Загадываете произвольное достаточно большое натуральное случайное число меньшее N, а я без проверки буду говорить, что оно не является простым, и с вероятностью
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{ln N - 1}{ln N}
буду прав. А при росте N эта вероятность стремится к 1.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 10:14     Алгоритм нахождения простых чисел #32
Thinker, да но я не говорил что он на всех числах правильно работает но до 264 все правильно делает

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

Добавлено через 2 минуты
есть и более надежный недетерминированный тест BPSW
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 10:24     Алгоритм нахождения простых чисел #33
Цитата Сообщение от aram_gyumri Посмотреть сообщение
откуда такая вероятность?
распределение простых чисел
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.07.2013, 12:54     Алгоритм нахождения простых чисел #34
Цитата Сообщение от Thinker Посмотреть сообщение
а я без проверки буду говорить, что оно не является простым
Только ваш алгоритм не сходится.
В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается.
Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 13:13     Алгоритм нахождения простых чисел #35
Цитата Сообщение от diagon Посмотреть сообщение
Только ваш алгоритм не сходится.
В сходящихся алгоритмах при увеличении числа раундов вероятность правильного ответа всегда повышается.
ну, это и так понятно, что в некоторых вероятностных алгоритмах вероятность зависит от некоторых параметров.
Цитата Сообщение от diagon Посмотреть сообщение
Если взять тест Миллера-Рабина и подставить в него 2(logn)^2, то вероятность правильного ответа достигнет 1 (не стремится, а именно достигнет). Это, правда, не совсем доказано, но все же.
видите, не доказано, значит это гипотеза, проверенная на конечном наборе чисел, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться.

а вообще, алгоритм получился со сложностью O(1), весело же
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.07.2013, 13:17     Алгоритм нахождения простых чисел #36
Цитата Сообщение от Thinker Посмотреть сообщение
а натуральных чисел бесконечно
В компьютере конечно.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 13:21     Алгоритм нахождения простых чисел #37
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
В компьютере конечно.
неужели?! так как (при использовании длинной арифметики и росте вычислительных возможностей) нет жесткого ограничения на диапазон рассматриваемых чисел, то замечание совсем не актуально.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.07.2013, 13:22     Алгоритм нахождения простых чисел #38
Цитата Сообщение от Thinker Посмотреть сообщение
видите, не доказано, значит это гипотеза, проверенная на конечном наборе числах, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться.
Она доказана, но зависит от этой штуки. А эта штука, между прочим, является проблемой тысячелетия, и за ее доказательство/опровержение дают 1000000$.
Т.е. если тест Миллера внезапно не сработает на каком-то числе, то это означает, что для этого числа не работает гипотеза Римана. А это значит, что вы можете получить 1000000$ (так как контрпример является опровержением).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.07.2013, 13:24     Алгоритм нахождения простых чисел
Еще ссылки по теме:

C++ Напишите программу нахождения всех трехзначных простых чисел
C++ Нахождения больших простых чисел
C++ Подскажите алгоритм подбора суммы простых чисел

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 13:24     Алгоритм нахождения простых чисел #39
Цитата Сообщение от diagon Посмотреть сообщение
Она доказана, но зависит от этой штуки.

Не по теме:

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

Yandex
Объявления
22.07.2013, 13:24     Алгоритм нахождения простых чисел
Ответ Создать тему
Опции темы

Текущее время: 17:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru