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

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

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

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

29.09.2012, 21:35. Просмотров 46648. Ответов 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;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
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....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Thinker
Эксперт C++
4225 / 2199 / 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
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:16  [ТС] #18
по поводу решета Эратосфена возможны вариации. Либо мы его строим один раз до начала всех проверок, а потом при проверке числа на простоту сначала проверяем делимость на 2, далее в нем ищем следующее простое число (ничего не вычеркивая, так как все ненужное уже вычеркнуто), проверяем делимость на него и так до корня из проверяемого числа. Либо сначала строится решето Эратосфена, а потом все простые числа из этого решета записываются в некоторый массив, а память из под решета освобождается. А массив из простых чисел будет для проверки на возможные делители. Безусловно, что такой алгоритм будет быстрее работать представленных выше, но все упирается в память. Пока вопрос стоит в написании функции для проверки на простоту чисел типа long long (алгоритмы выше легко для этого подходят при изменении типов переменных). А вот для решета Эратосфена для типа unigned long long нужно 4 Гб памяти, что не всегда подходит.
Поэтому задача состоит в том, чтобы написать быстрый детерминированный алгоритм для проверки одного-двух натуральных чисел, поэтому без решета Эратосфена
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
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;
Thinker
Эксперт C++
4225 / 2199 / 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
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.10.2012, 14:41  [ТС] #21
Хотел применить теорию, которая помогла написать более быстрый алгоритм для проверки на простоту, к построению решета Эратосфена. Но ни тут то было, самая быстрая реализация имеет такой вид

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Eratosfen(char *a, long n)
{
    long i, j, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        for(j = i << 1; j < n; j += i)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
а попытка ускорить данный алгоритм с помощью рассматриваемых выше модулей дает обратный эффект. Это и понятно почему.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.10.2012, 11:14  [ТС] #22
Решето Эратосфена в таком варианте
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Eratosfen(char *a, long n)
{
    long i, j, d, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        d = i << 1;
        for(j = 3 * i; j < n; j += d)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
работает в два раза быстрее предыдущего. Для первых 100 000 000 натуральных чисел алгоритм укладывается в секунду!

Добавлено через 1 час 56 минут
С подачи от valeriikozlov более быстрый алгоритм:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Eratosfen(char *a, long n)
{
    long i, j, d, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        d = i << 1;
        for(j = i * i; j < n; j += d)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
28.10.2012, 22:47 #23
не знаю на сколько актуально, но этот оптимизированный алгоритм можно загнать на GPU =) с лишь откидыванием четных чисел я получил скорость в проверки 10млрд делителей/ секунду. Число порядка 10^19 в худшем случае проверяет около 100-120ms.

Добавлено через 11 минут
Thinker, а ты еще что нить придумал ? вот конкретный тест:
digit 2305843009213693951
is simp 0
time 150.121 ms
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.10.2012, 09:07  [ТС] #24
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а ты еще что нить придумал ? вот конкретный тест:
digit 2305843009213693951
is simp 0
time 150.121 ms

Не по теме:

судя по всему, мои алгоритмы очень медленны для очень больших чисел. Вот в этой теме
Как проверить является ли число простым
всплыл более быстрый алгоритм AKS

AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
29.10.2012, 23:25 #25
Thinker, я так понял алгоритм никто не написал на с++? Просто тот же перебор можно оптимизировать для видеокарты и он будет работать с бешеной скоростью ю, пока достиг проверки 15млрд делителей/сек

Добавлено через 12 часов 1 минуту
Thinker, я придумал как ускорить этот алгоритм, произведя заранее подготовку, то есть имея какие то данные в виде таблицы в файле например, которые можно просчитать 1 раз и сохранить. В общем как ты писал, если исключить из проверки все четные числа и каждое 3е, то получим, что надо проверить всего 33% делителей. Я решил проверить на сколько уменьшится этот процент, если к примеру мы исключим по больше числе. В итоге получил такой расчет: при исключении всех простых чисел до 10 000 (а их 1228) получаем, что на больших числах нам надо проверить около 6,6% оставшихся, то есть можно ускорить в 5 раз! (теоритически). А период повторения этих чисел - их произведение = 808157282. То есть нужно получить все оставшиеся числа в промежутке от k (где k - первое число, которое не делится по модулю на 1228 простых) до k + 808157282. Судя по расчетам их около 53 млн - при размере u_int64 = 8 байт это занимает порядка 420 мб. Остается только получить эти числа =) ну или посчитать на сколько можно уменьшить данное количество.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
29.10.2012, 23:38 #26
Цитата Сообщение от AEXks Посмотреть сообщение
то есть имея какие то данные в виде таблицы в файле например,
Я не помню предлагал или нет
предварительно рассчитываем простые числа до 2^32 и записываем их в файл
это 16 гигабайт интов на самом деле меньше мы же не все туда будем записывать а только простые
можно создать файл для чисел 2^16 это 260 кБ (важна идея)
а потом при расчете если число попадает в диапазон берем из таблицы(из файла)
а если больше, то делим на делители из файла( т.е) делим только на простые числа
этим мы выбрасываем и кратные 2 и кратные 3 5, 7, 11 .......
скорость должна возрасти, хотя не просчитывал не знаю
основная работа ляжет на создание файла ( но это один раз)
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 09:10 #27
ValeryS, а что, если у нас число например порядка 10^19 = 2^19 * 5^19 и кончатся делители из файла?_)
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 09:35  [ТС] #28
AEXks, я уже ходил этим путем, прочитайте пост 16 этой темы. прироста в скорости нет. прирост в скорости начинается, если числа ОЧЕНЬ большие
При этом я рассматривал очень большие значения m, а чем ближе m к корню из тестируемого числа, тем больше убирается составных тестируемых чисел. например, если http://www.cyberforum.ru/cgi-bin/latex.cgi?m = \sqrt{a}, то остаются только простые тестируемые числа в роли потенциальных делителей. но реализация этого всего не позволяет добиться быстрой скорости, поэтому индийские ученые (AKS) пошли другим путем.

Дело же в чем. Мы же все равно фиксирует этот модуль m, а тестируемые числа могут быть сколь угодно большими, так и так возникнет процент лишних проверок с использованием составных делителей. да и реализовать это эффективно с массивами не удается.

ValeryS, такой алгоритм подойдет только для чисел из фиксированного диапазона, но не для произвольного числа.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
30.10.2012, 10:34 #29
Цитата Сообщение от AEXks Посмотреть сообщение
у нас число например порядка 10^19 = 2^19 * 5^19 и кончатся делители из файла?
это меньше чем 2^64 ???
Цитата Сообщение от Thinker Посмотреть сообщение
такой алгоритм подойдет только для чисел из фиксированного диапазона, но не для произвольного числа.
при использовании таблицы простых чисел до 2^32
можно проверять числа до 2^64
если этого мало то можно создать большую таблицу

вообще мне трудно решать,поскольку не могу представить прикладную задачу для применения таких больших простых чисел
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 10:59 #30
ValeryS, окей , задача состоит в взломе ключа RSA , длина которого как минимум 1000бит , так что тут даже не обойтись простой арифметикой, а вообще это все нужно для криптографии в том числе.
Thinker, Вы исходите из производительности одного ядра процессора, но на видеокарте это будет выглядеть по другому. Надо думать в этом направлении. И чем больше мы исключаем чисел, тем фактически большее количество делителей можно проверить за секунду. Пока, исключив только 2 и 3 я смог добиться проверки 16,6 млрд делителей в секунду. то есть 1,6 * 1010 / сек. Теперь по теоретическом расчету для проверки 232 делителей уйдет 232 / 1,6 * 1010 = 0,26 секунд. ( Что на практике так и есть, так как в 64 битное число можно как раз записать 20ти значные числа.)
ValeryS, То есть по рассуждениям выше не нужно ничего городить) числа 264 проверяются в худшем случае за 260ms , и в принципе можно считать , что для таких числе задача решена.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2012, 10:59
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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