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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 330, средняя оценка - 4.73
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 21:35     Быстрая проверка натурального числа на простоту #1
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 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;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2012, 21:35     Быстрая проверка натурального числа на простоту
Посмотрите здесь:

Проверка на простоту числа C++
Проверка числа на простоту C++
C++ ПРоверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Leomana
58 / 58 / 5
Регистрация: 29.06.2012
Сообщений: 188
29.09.2012, 21:47     Быстрая проверка натурального числа на простоту #2
интересно..
что лучше, код который краток и понятен или который быстрый, но в котором много буковок, переменных, и на первый взгляд вообще ужасающий?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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 сек.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
29.09.2012, 22:12     Быстрая проверка натурального числа на простоту #4
Мне кажется, ничего более быстрого не будет... Могу только предложить метод (возможно, очевидный) учета чисел, делимость на которые мы не проверяем:
Сделать массив из sqrt(n) элементов типа bool, инициализировать его нулями. Потом для каждого числа m, соответствующий элемент массива для которого равен 0, проверять делимость на него, а потом помечать все элементы вида m*k, где k -- целое, как не подлежащие проверке (единицой). Вроде должно работать, но кушает sqrt(n) бит памяти. Т.е., выигрыш по времени, проигрыш по памяти
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.09.2012, 22:22  [ТС]     Быстрая проверка натурального числа на простоту #5

Не по теме:

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



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

Не по теме:

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



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

Не по теме:

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

rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 183
29.09.2012, 23:19     Быстрая проверка натурального числа на простоту #10
Если кому интересно почитать статью : http://habrahabr.ru/post/124605/ там последний алгоритм за три секунды находит простые числа из 10 000 000 натуральных чисел.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.09.2012, 13:31  [ТС]     Быстрая проверка натурального числа на простоту #11
Цитата Сообщение от rinat_w Посмотреть сообщение
Если кому интересно почитать статью ... там последний алгоритм за три секунды находит простые числа из 10 000 000 натуральных чисел.
Цитата Сообщение от Thinker Посмотреть сообщение
третий алгоритм проверяет числа на простоту от 1 до 10 000 000 менее чем за 2 сек.
сравните
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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 простых числа, то здесь лучше подойдет упомянутое решето Эратосфена (по времени).
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 09:25  [ТС]     Быстрая проверка натурального числа на простоту #13
Замечу, что число лишних проверок с 74% можно увеличить, но для этого понадобится дополнительная память для хранения простых чисел из некоторого диапазона и хранения взаимно простых с заданным модулем чисел. Например, при m=2*3*5*7*11*13*17 понадобится до 100 мб дополнительной памяти, но алгоритм обещает быть быстрее третьего алгоритма. Если кого заинтересует такая реализация, пишите, будет время, реализую, там сложного ничего нет, просто надо аккуратно прописать все. А если все числа, которые требуется проверить на простоту, из наперед заданного диапазона, то, если память позволяет, в совокупности с решетом Эратосфена алгоритм совсем быстрым получается.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.10.2012, 09:38     Быстрая проверка натурального числа на простоту #14
Напомню, что размеры чисел, используемых в RSA (обычно не меньше 10308), исключают использование детерминированных алгоритмов ввиду их медленности. (Собсно, на этом RSA отчасти и держится.) Обычно довольствуются гарантией "99%, что это простое число", получаемой от всяких алгоритмов Миллера — Рабина.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
01.10.2012, 10:16     Быстрая проверка натурального числа на простоту #15
Цитата Сообщение от UFO94 Посмотреть сообщение
Т.е., выигрыш по времени, проигрыш по памяти
Не очевиден выигрыш
Цитата Сообщение от UFO94 Посмотреть сообщение
а потом помечать все элементы вида m*k, где k -- целое, как не подлежащие проверке (единицой).
для того чтобы пометить в массиве нужен цикл
для каждого числа свой(2,3,5.....)
т.е выбрасывая итерации из проверки мы добавляем служебный цикл



Цитата Сообщение от Thinker Посмотреть сообщение
спользовать в совокупности решето Этатосфена с проверкой на простоту, но вопрос в память, действительно, упирается.
тогда самое простое записать решето в виде массива
и вся "проверка"
C++
1
return arr[i];
решето можно записать в файл (или в несколько файлов, до 100 милионов второй от 100 до 200, и т.д.)
вся скорость будет зависеть от файловой системы
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 19:08  [ТС]     Быстрая проверка натурального числа на простоту #16
~OhMyGodSoLong~, про шифрование я уже писал, что там очень большие числа, поэтому эти алгоритмы не применимы там. Просто интересно написать быстрый детерминированный алгоритм для чисел, умещающихся в стандартные типы данных.
ValeryS, немного не то. если числа принадлежат некоторому диапазону (от 1 до R), то решето Эратосфена достаточно построить до корня из R, об этом речь, если для R памяти нет, а для корня из R есть. А иначе алгоритм проверки получится банальным.
При этом никаких лишних циклов не надо, решето Эратосфена до корня из R строится заранее

Добавлено через 7 часов 58 минут
Интересно, но если модуль увеличить, скажем m = 2*3*5*7*11 = 2310, то из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2...\sqrt{n}\} убираются из рассмотрения http://www.cyberforum.ru/cgi-bin/latex.cgi?100% - \frac{480}{2310}\cdot 100% \approx 80% элементов и алгоритм обещает быть быстрее, но есть одно НО... Взаимно простых чисел с модулем m (меньших m) будет 480, которые каждый раз надо на m увеличивать. Это требует использования массива. И такой алгоритм работает медленнее чем три приведенных выше. Поэтому пока третий алгоритм получился самым быстрым. Так что в сторону увеличения модуля (что гарантировало бы использования дополнительной памяти фиксированного размера независимо от тестируемых чисел, что есть хорошо) нет смысла идти.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
01.10.2012, 19:32     Быстрая проверка натурального числа на простоту #17
Цитата Сообщение от Thinker Посмотреть сообщение
ValeryS, немного не то. если числа принадлежат некоторому диапазону (от 1 до R), то решето Эратосфена достаточно построить до корня из R,
я разве спорю
просто
UFO94, предлагает его строить каждый раз
Цитата Сообщение от UFO94 Посмотреть сообщение
Сделать массив из sqrt(n) элементов типа bool, инициализировать его нулями. Потом для каждого числа m, соответствующий элемент массива для которого равен 0, проверять делимость на него, а потом помечать все элементы вида m*k, где k -- целое, как не подлежащие проверке (единицой).
т.е как я понял
проверили не делится на двойку вычеркнули из доп массива все кратное 2
проверили на 3 вычеркнули все кратное тройке
и при каждой проверки числа мы заново заполняем этот массив

я же предлагаю табличный метод, самый быстрый но и памяти жрет много
тут уж зависит от задачи
одно дело проверить пару чисел за программу, другое каждую секунду проверять кучу чисел
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:16  [ТС]     Быстрая проверка натурального числа на простоту #18
по поводу решета Эратосфена возможны вариации. Либо мы его строим один раз до начала всех проверок, а потом при проверке числа на простоту сначала проверяем делимость на 2, далее в нем ищем следующее простое число (ничего не вычеркивая, так как все ненужное уже вычеркнуто), проверяем делимость на него и так до корня из проверяемого числа. Либо сначала строится решето Эратосфена, а потом все простые числа из этого решета записываются в некоторый массив, а память из под решета освобождается. А массив из простых чисел будет для проверки на возможные делители. Безусловно, что такой алгоритм будет быстрее работать представленных выше, но все упирается в память. Пока вопрос стоит в написании функции для проверки на простоту чисел типа long long (алгоритмы выше легко для этого подходят при изменении типов переменных). А вот для решета Эратосфена для типа unigned long long нужно 4 Гб памяти, что не всегда подходит.
Поэтому задача состоит в том, чтобы написать быстрый детерминированный алгоритм для проверки одного-двух натуральных чисел, поэтому без решета Эратосфена
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
01.10.2012, 21:23     Быстрая проверка натурального числа на простоту #19
Цитата Сообщение от Thinker Посмотреть сообщение
unigned long long нужно 4 Гб
чей то ты приуменьшил
4 Гб для unigned long (32 бита) можно 500 Мб (используя битовые маски)
а unigned long long 64 бита 16 *10^18 даже не знаю приставки(экза?) бит
разумеется я говорю о 32 разрядных ОС и о табличном методе
я даже не могу представить прикладную задачу для таких чисел, если это не чисто математическая проблема

Добавлено через 4 минуты
я правильно понял твой алгоритм
в массиве решето(массив простых чисел)
C++
1
2
3
4
5
6
for(unsigned int i=0;i<k;i++)
   {
     if(n%arrEr[i]==0)
         return false;
   }
return true;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2012, 21:26     Быстрая проверка натурального числа на простоту
Еще ссылки по теме:

проверка числа на простоту C++
C++ Проверка на простоту числа - исправить ошибки в коде
C++ Проверка числа на простоту

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 21:26  [ТС]     Быстрая проверка натурального числа на простоту #20
4 Гб для типа unigned long long c учетом, что решето будет до корня из ULLONG_MAX. Алгоритм что-то типа этого, где k - такое значение, что arrEr[k-1]*arrEr[k-1] <= n
Yandex
Объявления
01.10.2012, 21:26     Быстрая проверка натурального числа на простоту
Ответ Создать тему
Опции темы

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