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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
#1

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

29.09.2012, 21:35. Просмотров 46972. Ответов 90
Метки нет (Все метки)

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}, то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}
В данном алгоритме из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}, которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}
Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
28
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2012, 21:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая проверка натурального числа на простоту (C++):

Проверка числа на простоту - C++
я реализовал вот так, но алгоритм очень долгий, мне надо проверять очень большое количество чисел (десятки тысяч) и он так надолго виснет...

Проверка числа на простоту - C++
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N на простоту. N вводится с клавиатуры. ...

Проверка числа на простоту - C++
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число...

Проверка на простоту числа - C++
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь через оператор switch case: т е, case...

Проверка числа на простоту - C++
Написать программу, которая запрашивает массив натуральных чисел (ввод с клавиатуры), а затем выводит на экран те элементы массива, которые...

Проверка числа на простоту - C++
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)? P.S....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Leomana
58 / 58 / 5
Регистрация: 29.06.2012
Сообщений: 188
29.09.2012, 21:47 #2
интересно..
что лучше, код который краток и понятен или который быстрый, но в котором много буковок, переменных, и на первый взгляд вообще ужасающий?
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 21:52  [ТС] #3
проверку на простоту можно в одну строчку написать (для a>=2)
C++
1
2
3
4
int Prime(unsigned long a, unsigned long i)
{
   return i*i <= a ? (a%i) && Prime(a, i + 1) : 1;
}
и вызывать Prime(a, 2). Кратко и понятно, только толку от него почти никакого. А вот третий алгоритм проверяет числа на простоту от 1 до 10 000 000 менее чем за 2 сек.
2
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
29.09.2012, 22:12 #4
Мне кажется, ничего более быстрого не будет... Могу только предложить метод (возможно, очевидный) учета чисел, делимость на которые мы не проверяем:
Сделать массив из sqrt(n) элементов типа bool, инициализировать его нулями. Потом для каждого числа m, соответствующий элемент массива для которого равен 0, проверять делимость на него, а потом помечать все элементы вида m*k, где k -- целое, как не подлежащие проверке (единицой). Вроде должно работать, но кушает sqrt(n) бит памяти. Т.е., выигрыш по времени, проигрыш по памяти
1
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 22:22  [ТС] #5

Не по теме:

Leomana, Вы как девушка, может напишите более красивый алгоритм
P.S. В третьем алгоритме массивы не используются, так как они только тормозят процесс, именно поэтому не стал рассматривать случаи 2*3*5*...



Добавлено через 8 минут
UFO94, вариант хороший и понятный использовать в совокупности решето Этатосфена с проверкой на простоту, но вопрос в память, действительно, упирается. Но, как вариант, попробуйте для сравнения
0
Leomana
58 / 58 / 5
Регистрация: 29.06.2012
Сообщений: 188
29.09.2012, 22:29 #6
[QUOTE=Thinker;3501837]

Не по теме:

Leomana, Вы как девушка, может напишите более красивый алгоритм
P.S. В третьем алгоритме массивы не используются, так как они только тормозят процесс, именно поэтому не стал рассматривать случаи 2*3*5*...



куда уж краше
хм.. надо запомнить такую печальную вещь о массиве))
Мне вот еще интересно.. где же может появится необходимость узнать простое ли число?
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 22:35  [ТС] #7
Цитата Сообщение от Leomana Посмотреть сообщение
Мне вот еще интересно.. где же может появится необходимость узнать простое ли число?
Криптография с открытым ключом (правда там ОЧЕНЬ большие простые числа), цифровые подписи, схемы разделения секрета, кольца вычетов, конечные поля, теория чисел и т.д.
1
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
29.09.2012, 22:50 #8
Thinker, а ты коварен) Хочешь быстро раскладывать на множители и заставить математиков придумывать в криптографии что-то кардинально новое?)
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 22:58  [ТС] #9
Цитата Сообщение от UFO94 Посмотреть сообщение
Хочешь быстро раскладывать на множители и заставить математиков придумывать в криптографии что-то кардинально новое?)

Не по теме:

вы о взломе шифров. нет, все это не подойдет, так как в реальных шифрах числа ОЧЕНЬ большие и все известные методы взлома шифров с открытым ключом имеют эспоненциальную сложность. тем более, в серьезных шифрах с открытым ключом и цифровых подписях используются эллиптические кривые, а там другие методы шифрования. так что мне просто интересны детерминированные алгоритмы проверки на простоту, не более. Тем более они меня сегодня заинтересовали, завтра другое заинтересует, наверное.
вы, наверное, RSA имеете ввиду. Там задача о факторизации, немного другое, нежели эта тема.
А кардинально "новое" это эллиптические кривые, они дают очень хороший эффект и используются очень успешно. Правда в RSA они эффекта не дают. Поэтому до сих пор RSA зависит от сложности задачи факторизации

0
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
29.09.2012, 23:19 #10
Если кому интересно почитать статью : http://habrahabr.ru/post/124605/ там последний алгоритм за три секунды находит простые числа из 10 000 000 натуральных чисел.
1
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.09.2012, 13:31  [ТС] #11
Цитата Сообщение от rinat_w Посмотреть сообщение
Если кому интересно почитать статью ... там последний алгоритм за три секунды находит простые числа из 10 000 000 натуральных чисел.
Цитата Сообщение от Thinker Посмотреть сообщение
третий алгоритм проверяет числа на простоту от 1 до 10 000 000 менее чем за 2 сек.
сравните
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.09.2012, 20:07 #12
Цитата Сообщение от rinat_w Посмотреть сообщение
Если кому интересно почитать статью : http://habrahabr.ru/post/124605/ там последний алгоритм за три секунды находит простые числа из 10 000 000 натуральных чисел.
На самом деле это две совсем разные задачи, хотя в обоих случаях идет речь о простых числах.
Если нужно проверить натуральное число на простоту, то тут лучше подходит вариант Thinker (по времени).
Если же нужно найти все простые числа в диапазоне от 1 до N или если нужно найти первые N простых числа, то здесь лучше подойдет упомянутое решето Эратосфена (по времени).
2
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 09:25  [ТС] #13
Замечу, что число лишних проверок с 74% можно увеличить, но для этого понадобится дополнительная память для хранения простых чисел из некоторого диапазона и хранения взаимно простых с заданным модулем чисел. Например, при m=2*3*5*7*11*13*17 понадобится до 100 мб дополнительной памяти, но алгоритм обещает быть быстрее третьего алгоритма. Если кого заинтересует такая реализация, пишите, будет время, реализую, там сложного ничего нет, просто надо аккуратно прописать все. А если все числа, которые требуется проверить на простоту, из наперед заданного диапазона, то, если память позволяет, в совокупности с решетом Эратосфена алгоритм совсем быстрым получается.
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.10.2012, 09:38 #14
Напомню, что размеры чисел, используемых в RSA (обычно не меньше 10308), исключают использование детерминированных алгоритмов ввиду их медленности. (Собсно, на этом RSA отчасти и держится.) Обычно довольствуются гарантией "99%, что это простое число", получаемой от всяких алгоритмов Миллера — Рабина.
0
ValeryS
Модератор
6634 / 5041 / 466
Регистрация: 14.02.2011
Сообщений: 16,851
01.10.2012, 10:16 #15
Цитата Сообщение от UFO94 Посмотреть сообщение
Т.е., выигрыш по времени, проигрыш по памяти
Не очевиден выигрыш
Цитата Сообщение от UFO94 Посмотреть сообщение
а потом помечать все элементы вида m*k, где k -- целое, как не подлежащие проверке (единицой).
для того чтобы пометить в массиве нужен цикл
для каждого числа свой(2,3,5.....)
т.е выбрасывая итерации из проверки мы добавляем служебный цикл



Цитата Сообщение от Thinker Посмотреть сообщение
спользовать в совокупности решето Этатосфена с проверкой на простоту, но вопрос в память, действительно, упирается.
тогда самое простое записать решето в виде массива
и вся "проверка"
C++
1
return arr[i];
решето можно записать в файл (или в несколько файлов, до 100 милионов второй от 100 до 200, и т.д.)
вся скорость будет зависеть от файловой системы
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2012, 10:16
Привет! Вот еще темы с ответами:

Проверка числа на простоту - C++
Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно ...

Проверка числа на простоту - C++
Помогите написать программу которая проверяет простое число или нет.

Проверка числа на простоту (нужны комментарии) - C++
объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее bool Prime(int const num)//...

Робота с динамической памятью, проверка числа на простоту - C++
В динамическую память последовательно занести введенные с клавиатуры целые числа (признак завершения ввода - число ноль). Проверить все...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.10.2012, 10:16
Ответ Создать тему
Опции темы

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