Форум программистов, компьютерный форум 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++ Проверка числа на простоту
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
30.10.2012, 23:21     Быстрая проверка натурального числа на простоту #41
Цитата Сообщение от AEXks Посмотреть сообщение
А все таки как определить номер старшего бита числа, кроме как

C++
1
2
3
4
5
for( ; dig != 0; )
{
 dig >>= 1;
 ++sum;
}
ну можно попробовать так
C++
1
2
3
4
5
6
7
8
9
10
11
for( ; dig != 0; )
{
 dig >>= 8;
 mod= dig&0xFF;
 sum+=8;
}
for( ; mod != 0; )
{
 mod >>= 1;
 ++sum;
}
при числе 0хFFFFFFFFFFFFFFFF
должно получится 16 циклов вместо 64
между ними можно сдвигать еще на 4,2
можно начать сдвигать с 16 с 32

Добавлено через 2 минуты
если первый цикл сделать сдвиг на 32
потом 16,8,4,2,1
то в самом пиковом случае 12 циклов(если я правильно подсчитал)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 11:13     Быстрая проверка натурального числа на простоту #42
ValeryS, попробуем

Добавлено через 21 минуту
ValeryS, что то пример работает не верно. Наверно вы не проверяли результат. В общем вот так надо
C++
1
2
3
4
5
6
7
8
9
10
for( ; dig >= 0xFF; )
{
    dig >>= 8;          
    sum += 8;
}
for( ; dig != 0; )
{
    dig >>= 1;
    ++sum;
}
Для числа, у которого 44 старший бит получаем:
- стандартный алгоритм - 44 битовых операции
- усовершенствованный - 5 + 4 = 9 битовых операций
А для больших чисел наверно можно и увеличить ширину сдвига. Но тогда чем больше ширина сдвига, тем больше нужно сделать сдвигов для маленьких чисел.
Например для самого большого числа в 63 бит:
- при сдвиге в 8 получаем 7 + 7 = 14 БО
- при сдвиге в 16 получаем 3 + 15 = 18 БО
- при сдвиге в 32 получаем 1 + 31 = 32 БО

Думаю 8 это оптимально.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 12:03  [ТС]     Быстрая проверка натурального числа на простоту #43
можно использовать двоичный поиск. сложность алгоритма
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// n - количество бит в числе a
int Search(unsigned long long a, int n)
{
   int i = 0;
   while (n)
   {
       n >>= 1;
       if (a >> n)
       {
           i += n;
           a >>= n;
       }
   }
   return i;
}
в среднем будет O(ln n). А сложность алгоритма
C++
1
2
3
4
5
6
7
int Search(unsigned long long a)
{
   int i;
   for(i = -1; a; a >>= 1, i++)
      ;
   return i;
}
в среднем будет O(n). Поэтому первый алгоритм в среднем работает в разы быстрее второго.

Первый алгоритм максимум сделает 6 проверок, второй - 64 проверки. почувствуйте разницу.

Добавлено через 14 минут
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых.
Я Вам про этот модуль m и писал в предыдущих постах. Увеличивал я именного его. Это и есть период. Странно, а я думал, что Вы понимали меня))
Catstail
Модератор
 Аватар для Catstail
21493 / 10246 / 1669
Регистрация: 12.02.2012
Сообщений: 17,134
31.10.2012, 12:30     Быстрая проверка натурального числа на простоту #44
Вы будете смеяться... Но самый быстрый алгоритм проверки числа (до 10000) на простоту, на мой взгляд, таков:

Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" !
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 12:35  [ТС]     Быстрая проверка натурального числа на простоту #45
Catstail, смеяться никто не будет. При любом модуле m именно это и происходит при проверке всех простых чисел, меньших числа m (именно двоичный поиск). Это все понятно и просто. самое интересное начинается, когда простые числа в массиве заканчиваются, а проверка на делители продолжается)))
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 13:04     Быстрая проверка натурального числа на простоту #46
Catstail, в этой теме рассматриваются числа уже больше чем 1000, а именно как минимум _int64, и для этих числе я решил задачу ( читайте выше) А щас надо попытаться сделать длинное деление по модулю

Добавлено через 5 минут
Thinker, сложность то будет немного другая , я бы сказал O(ln n) * 2 так как вы в проверке еще сдвиги делаете и еще проверок в два раза больше - в цикле и для того чтобы суммировать.. в общем надо уже на практике заменять разные реализации и при прочих равных условиях посмотреть что получится) ок. Попробую
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 13:09  [ТС]     Быстрая проверка натурального числа на простоту #47
AEXks,
O(ln n)*2 = O(ln n)
алгоритмы я протестировал для интереса, в среднем, первый работает минимум в 3 раза быстрее второго, а иначе не стал бы его здесь выставлять)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
31.10.2012, 13:39     Быстрая проверка натурального числа на простоту #48
Цитата Сообщение от AEXks Посмотреть сообщение
ValeryS, что то пример работает не верно. Наверно вы не проверяли результат.
писал ночью на память вот и пропустил строку( да и порядок строк попутал)
поскольку цикл лишний раз крутится нужна компенсация
в общем вот проверка четырех алгоритмов два моих и два твоих(все работает идентично)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include "stdafx.h"
int MyAlgor(unsigned long long dig)
{
int sum;
unsigned int mod;
for(sum=0 ; dig != 0;  sum+=8)
  {
   
   mod= dig&0xFF;
   dig >>= 8;
   }
sum-=8;
for( ; mod != 0;sum++ )
{
 mod >>= 1;
}
return sum;
}
int My1Algor(unsigned long long dig)
{
    int sum;
    unsigned int mod;
for(sum=0 ; dig !=0;  sum+=32)
  {
   mod= dig&0xFFFFFFFF;
   dig >>= 32;
   }
sum-=32;
 
dig=mod;
for(; dig!=0;  sum+=16)
  {
   mod= dig&0xFFFF;  
  dig >>= 16;
  }
sum-=16;
dig=mod;
for(; dig != 0;  sum+=8)
  {
    mod= dig&0xFF;
     dig >>=8;
  
   }
sum-=8;
dig=mod;
for(; dig != 0;  sum+=4)
  {
     mod= dig&0x0F;
      dig >>= 4;
   
   }
sum-=4;
dig=mod;
for(; dig != 0;  sum+=2)
  {
      mod= dig&0x3;  
      dig >>= 2;
  
   }
sum-=2;
dig=mod;
for( ; mod != 0;sum++ )
{
 mod >>= 1;
}
return sum;
}
int AEXksAlgor(unsigned long long dig)
{
int sum=0;
    for( ; dig != 0; )
{
     dig >>= 1;
     ++sum;
} 
    return sum;
}
int AEXksHiAlgor(unsigned long long dig)
{
int sum=0;
for( ; dig >= 0xFF; )
{
    dig >>= 8;          
    sum += 8;
}
for( ; dig != 0; )
{
    dig >>= 1;
    ++sum;
}
return sum;
}
int _tmain(int argc, _TCHAR* argv[])
{
   printf("%d %d %d %d\n",MyAlgor(-1),My1Algor(-1),AEXksAlgor(-1),AEXksHiAlgor(-1));
   printf("%d %d %d %d\n",MyAlgor(1),My1Algor(1),AEXksAlgor(1),AEXksHiAlgor(1));
   for(int i=0;i<32;i++)
   {
     printf("------------- i=%d --------------\n",i);   
     printf("%d %d %d %d \n",MyAlgor(1<<i),My1Algor(1<<i),AEXksAlgor(1<<i),AEXksHiAlgor(1<<i));
    printf("---------------------------\n");
   }
    return 0;
}
Цитата Сообщение от Catstail Посмотреть сообщение
Но самый быстрый алгоритм проверки числа (до 10000) на простоту, на мой взгляд, таков:
Создать упорядоченный массив всех простых чисел от 2 до 9973
вообще то здесь речь шла о числах как минимум 2 в 64 прикинь размер массива
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 13:48     Быстрая проверка натурального числа на простоту #49
Thinker, а как проводились тестирования?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
31.10.2012, 13:49     Быстрая проверка натурального числа на простоту #50
Цитата Сообщение от AEXks Посмотреть сообщение
Но тогда чем больше ширина сдвига, тем больше нужно сделать сдвигов для маленьких чисел.
не будет сдвигов по твоему алгоритму
Цитата Сообщение от AEXks Посмотреть сообщение
for( ; dig >= 0xFF; )
число меньше чем 0xFF в цикл не входим

если скрестить мой второй алгоритм (My1Algor) и твой (AEXksHiAlgor) то для _int64 можно наверное вообще без циклов обойтись, только проверки(if)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 13:56  [ТС]     Быстрая проверка натурального числа на простоту #51
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а как проводились тестирования?
просто прогнал все числа от 2 до 100 000 000 на время) ну и, конечно, теоретически видно из сложности алгоритмов.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 14:15     Быстрая проверка натурального числа на простоту #52
ValeryS, там выше есть уже этот алгоритм)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
31.10.2012, 14:19     Быстрая проверка натурального числа на простоту #53
мои алгоритмы врут при 0

Цитата Сообщение от ValeryS Посмотреть сообщение
если скрестить мой второй алгоритм (My1Algor) и твой (AEXksHiAlgor) то для _int64 можно наверное вообще без циклов обойтись, только проверки(if)
вот накидал
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int MyAlgorIf(unsigned long long dig)
{
int sum=0;
if(dig>0xFFFFFFFF)
{
 dig>>=32;
 sum+=32;
}
if(dig>0xFFFF)
{
 dig>>=16;
 sum+=16;
}
if(dig>0xFF)
{
 dig>>=8;
 sum+=8;
}
if(dig>0xF)
{
 dig>>=4;
 sum+=4;
}
if(dig>0x3)
{
 dig>>=2;
 sum+=2;
}
if(dig>0x1)
{
 dig>>=1;
 sum+=1;
}
if(dig)
{
 dig>>=1;
 sum+=1;
}
return sum;
}
Цитата Сообщение от AEXks Посмотреть сообщение
ValeryS, там выше есть уже этот алгоритм)
ты сейчас про какой??(хоть номер поста указывай)
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 14:24     Быстрая проверка натурального числа на простоту #54
ValeryS, #43
Catstail
Модератор
 Аватар для Catstail
21493 / 10246 / 1669
Регистрация: 12.02.2012
Сообщений: 17,134
31.10.2012, 14:48     Быстрая проверка натурального числа на простоту #55
Цитата Сообщение от ValeryS Посмотреть сообщение
вообще то здесь речь шла о числах как минимум 2 в 64 прикинь размер массива
- а это так просто, "прикинуть"? И потом, если простые числа нужны для каких-либо приложений, их диапазон "по-любому" ограничен. Поэтому целесообразно один раз массив сформировать, а потом пользоваться.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 14:59  [ТС]     Быстрая проверка натурального числа на простоту #56
Catstail, в криптографии нет ограничений. Там по принципу "чем сложнее, тем лучше". Поэтому ограничений на длину простых чисел тоже нет, чем длиннее, тем лучше. На этом базируется сложность вскрытия ассимметричных шифров, схем разделения секрета и т.д. Никакой массив не уместит столько простых чисел, чтобы перечислить все простые числа, которые могут быть использованы, например в RSA.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 15:43     Быстрая проверка натурального числа на простоту #57
Catstail, тем более чтение из огроменного массива будет занимать много времени, так как не все время же это будет находиться в ОЗУ. По этому это не вариант.

Добавлено через 1 минуту
Catstail, а прикинуть не сложно. Например взять 100 000 000 чисел - 100 000 000* 8 / 1024 /1024 = 7,6 мб , соответственно 1млрд - около 7,6 * 100 = 7600 мб
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 16:19  [ТС]     Быстрая проверка натурального числа на простоту #58
AEXks, немного не то. Количество простых чисел от 2 до n примерно равно
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n}{\ln n}
поэтому при n = 100 000 000 нужно примерно 45 мб.,
при n = 1 000 000 000 нужно 390 мб. и т.д.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 23:00     Быстрая проверка натурального числа на простоту #59
Thinker, столкнулся с некоторыми проблемами при реализации длинного деления по модулю.
1) почему то битовые операции работают только с 32х разрядными числами и не хотят сдвигать на 32 33 и выше.
2) как делить по модулю на составное число (реализовал только массив на uint)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2012, 08:39     Быстрая проверка натурального числа на простоту
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
01.11.2012, 08:39     Быстрая проверка натурального числа на простоту #60
Цитата Сообщение от AEXks Посмотреть сообщение
почему то битовые операции работают только с 32х разрядными числами и не хотят сдвигать на 32 33 и выше.
позвольте не поверить
C++
1
2
3
unsigned long long mn =(unsigned long long)-1;
    for(int i=32; i<64;i++)
        printf("%x \n",mn>>i);
прекрасно работает
но все дело в
C++
1
unsigned
при знаковых числах копируется знаковый бит
0хFF знаковый бит 1
сдвигаем 0xFF>>1 получаем 0x7F
добавляем знаковый бит 0xFF
от чего ушли к тому пришли
Yandex
Объявления
01.11.2012, 08:39     Быстрая проверка натурального числа на простоту
Ответ Создать тему
Опции темы

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