Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
ALEXKIRNAS
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
#1

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

21.07.2013, 16:52. Просмотров 3619. Ответов 38
Метки нет (Все метки)

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

C++
1
if(x%2 && x%3 && x%5 && x%7) std::cout << "Число простое!\n";
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2013, 16:52
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм нахождения простых чисел (C++):

Алгоритм нахождения простых чисел
Не могу найти в интернете нормальный код алгоритма нахождения простых чисел....

Алгоритм нахождения простых чисел
Не так давно начал изучать с++. Вот попытался написать программу которая...

Алгоритм нахождения ПРОСТЫХ чисел в файле
Заполнить файл f целыми числами, полученными с помощью генератора случайных...

Программа нахождения простых чисел
Я написал программу но в ней ошибка! Не пойму какая! Но мне важно понять как...

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

Написать программу нахождения первых 50 простых чисел
Написать программу нахождения первых 50 простых чисел...Помогите пожалустно...

38
Kuzia domovenok
2212 / 1981 / 443
Регистрация: 25.03.2012
Сообщений: 6,960
Записей в блоге: 1
21.07.2013, 18:41 #21
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
101
я уверен, имелись в виду числа до 100
0
dr.curse
392 / 348 / 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
Retyrn0
45 / 45 / 5
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
21.07.2013, 19:01 #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
я уверен, имелись в виду числа до 100
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...

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

Добавлено через 1 минуту
Цитата Сообщение от aram_gyumri Посмотреть сообщение
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
Я осознал свою ошибку, прошу прощения)
1
Kuzia domovenok
2212 / 1981 / 443
Регистрация: 25.03.2012
Сообщений: 6,960
Записей в блоге: 1
21.07.2013, 19:02 #24
Цитата Сообщение от Retyrn0 Посмотреть сообщение
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...
не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.
0
ValeryS
Модератор
7134 / 5402 / 669
Регистрация: 14.02.2011
Сообщений: 18,225
21.07.2013, 19:12 #25
Цитата Сообщение от salam Посмотреть сообщение
if(n & 1 == 0) return false;
число 2 покажет как не простое
добавить бы надо
0
dr.curse
392 / 348 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 20:53 #26
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Тут логическая игра слов с толку немного сбивает.
учи матеметику кузя, это некакая не игра слов
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 20:59 #27
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Нужно чтобы алгоритм был быстрым
http://www.cyberforum.ru/cpp-beginners/thread660361.html
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
22.07.2013, 05:34 #28
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
не надо, пожалуйста, обвинять Википедию в ваших логических ошибках.
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 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, выигрыш - сотые доли секунды. А вот если уменьшить количество лишних проверок, то можно скорость в разы увеличить.
0
dr.curse
392 / 348 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 09:46 #30
а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log3n), если память не изменяет то была задачка проверки на простоту чисел <264 и решалaсь она миллером-рабином
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 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.
0
dr.curse
392 / 348 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 10:14 #32
Thinker, да но я не говорил что он на всех числах правильно работает но до 264 все правильно делает

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

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

а вообще, алгоритм получился со сложностью O(1), весело же
0
Kuzia domovenok
2212 / 1981 / 443
Регистрация: 25.03.2012
Сообщений: 6,960
Записей в блоге: 1
22.07.2013, 13:17 #36
Цитата Сообщение от Thinker Посмотреть сообщение
а натуральных чисел бесконечно
В компьютере конечно.
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 13:21 #37
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
В компьютере конечно.
неужели?! так как (при использовании длинной арифметики и росте вычислительных возможностей) нет жесткого ограничения на диапазон рассматриваемых чисел, то замечание совсем не актуально.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.07.2013, 13:22 #38
Цитата Сообщение от Thinker Посмотреть сообщение
видите, не доказано, значит это гипотеза, проверенная на конечном наборе числах, а натуральных чисел бесконечно, поэтому к гипотезам нужно с осторожностью относиться.
Она доказана, но зависит от этой штуки. А эта штука, между прочим, является проблемой тысячелетия, и за ее доказательство/опровержение дают 1000000$.
Т.е. если тест Миллера внезапно не сработает на каком-то числе, то это означает, что для этого числа не работает гипотеза Римана. А это значит, что вы можете получить 1000000$ (так как контрпример является опровержением).
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 13:24 #39
Цитата Сообщение от diagon Посмотреть сообщение
Она доказана, но зависит от этой штуки.

Не по теме:

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

0
22.07.2013, 13:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.07.2013, 13:24
Привет! Вот еще темы с решениями:

Программа для нахождения простых чисел от 1 до 100
Здравствуйте, в задании требуется написать программу для нахождения простых...

Напишите программу нахождения всех трехзначных простых чисел
Найти все трехзначные простые числа

Алгоритм отбора простых чисел
Сижу учу С++ по Шилтду (Базовый курс) И вот папался такой алгоритм, на...

Алгоритм поиска простых чисел
Доброго времени суток. Помогите пожалуйста с алгоритмом поиска простых чисел в...


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

Или воспользуйтесь поиском по форуму:
39
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru