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

@Thinker · Регистрация: 26.08.2011

Студворк — интернет-сервис помощи студентам

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

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее $https://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;
}

В данном алгоритме из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества $https://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;
}

Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.

ValeryS · 30.10.2012, 23:21

Сообщение от 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 · 31.10.2012, 11:13

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 · 31.10.2012, 12:03 **[ТС]**

можно использовать двоичный поиск. сложность алгоритма

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 · 31.10.2012, 12:30

Вы будете смеяться... Но самый быстрый алгоритм проверки числа (до 10000) на простоту, на мой взгляд, таков:

Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" !

@Thinker · 31.10.2012, 12:35 **[ТС]**

Catstail, смеяться никто не будет. При любом модуле m именно это и происходит при проверке всех простых чисел, меньших числа m (именно двоичный поиск). Это все понятно и просто. самое интересное начинается, когда простые числа в массиве заканчиваются, а проверка на делители продолжается)))

@AEXks · 31.10.2012, 13:04

Catstail, в этой теме рассматриваются числа уже больше чем 1000, а именно как минимум _int64, и для этих числе я решил задачу ( читайте выше) А щас надо попытаться сделать длинное деление по модулю

Добавлено через 5 минут
Thinker, сложность то будет немного другая , я бы сказал O(ln n) * 2 так как вы в проверке еще сдвиги делаете и еще проверок в два раза больше - в цикле и для того чтобы суммировать.. в общем надо уже на практике заменять разные реализации и при прочих равных условиях посмотреть что получится) ок. Попробую

@Thinker · 31.10.2012, 13:09 **[ТС]**

AEXks,
O(ln n)*2 = O(ln n)
алгоритмы я протестировал для интереса, в среднем, первый работает минимум в 3 раза быстрее второго, а иначе не стал бы его здесь выставлять)

ValeryS · 31.10.2012, 13:39

Сообщение от 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 · 31.10.2012, 13:48

Thinker, а как проводились тестирования?

ValeryS · 31.10.2012, 13:49

Сообщение от AEXks

Но тогда чем больше ширина сдвига, тем больше нужно сделать сдвигов для маленьких чисел.

не будет сдвигов по твоему алгоритму

Сообщение от AEXks

for( ; dig >= 0xFF; )

число меньше чем 0xFF в цикл не входим

если скрестить мой второй алгоритм (My1Algor) и твой (AEXksHiAlgor) то для _int64 можно наверное вообще без циклов обойтись, только проверки(if)

@Thinker · 31.10.2012, 13:56 **[ТС]**

Сообщение от AEXks

Thinker, а как проводились тестирования?

просто прогнал все числа от 2 до 100 000 000 на время) ну и, конечно, теоретически видно из сложности алгоритмов.

@AEXks · 31.10.2012, 14:15

ValeryS, там выше есть уже этот алгоритм)

ValeryS · 31.10.2012, 14:19

мои алгоритмы врут при 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 · 31.10.2012, 14:24

ValeryS, #43

@Catstail · 31.10.2012, 14:48

Сообщение от ValeryS

вообще то здесь речь шла о числах как минимум 2 в 64 прикинь размер массива

- а это так просто, "прикинуть"? И потом, если простые числа нужны для каких-либо приложений, их диапазон "по-любому" ограничен. Поэтому целесообразно один раз массив сформировать, а потом пользоваться.

@Thinker · 31.10.2012, 14:59 **[ТС]**

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

@AEXks · 31.10.2012, 15:43

Catstail, тем более чтение из огроменного массива будет занимать много времени, так как не все время же это будет находиться в ОЗУ. По этому это не вариант.

Добавлено через 1 минуту
Catstail, а прикинуть не сложно. Например взять 100 000 000 чисел - 100 000 000* 8 / 1024 /1024 = 7,6 мб , соответственно 1млрд - около 7,6 * 100 = 7600 мб

@Thinker · 31.10.2012, 16:19 **[ТС]**

AEXks, немного не то. Количество простых чисел от 2 до n примерно равно
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n}{\ln n}$
поэтому при n = 100 000 000 нужно примерно 45 мб.,
при n = 1 000 000 000 нужно 390 мб. и т.д.

@AEXks · 31.10.2012, 23:00

Thinker, столкнулся с некоторыми проблемами при реализации длинного деления по модулю.
1) почему то битовые операции работают только с 32х разрядными числами и не хотят сдвигать на 32 33 и выше.
2) как делить по модулю на составное число (реализовал только массив на uint)

ValeryS · 01.11.2012, 08:39

Сообщение от 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
от чего ушли к тому пришли

Новые блоги и статьи Все статьи Все блоги /
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений

@Catstail Супер-модератор 38209 / 21142 / 4312 Регистрация: 12.02.2012 Сообщений: 34,755 Записей в блоге: 14
	31.10.2012, 12:30
	Вы будете смеяться... Но самый быстрый алгоритм проверки числа (до 10000) на простоту, на мой взгляд, таков: Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" ! 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	31.10.2012, 12:35 [ТС]
	Catstail, смеяться никто не будет. При любом модуле m именно это и происходит при проверке всех простых чисел, меньших числа m (именно двоичный поиск). Это все понятно и просто. самое интересное начинается, когда простые числа в массиве заканчиваются, а проверка на делители продолжается))) 1

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 13:04
	Catstail, в этой теме рассматриваются числа уже больше чем 1000, а именно как минимум _int64, и для этих числе я решил задачу ( читайте выше) А щас надо попытаться сделать длинное деление по модулю Добавлено через 5 минут Thinker, сложность то будет немного другая , я бы сказал O(ln n) * 2 так как вы в проверке еще сдвиги делаете и еще проверок в два раза больше - в цикле и для того чтобы суммировать.. в общем надо уже на практике заменять разные реализации и при прочих равных условиях посмотреть что получится) ок. Попробую 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	31.10.2012, 13:09 [ТС]
	AEXks, O(ln n)*2 = O(ln n) алгоритмы я протестировал для интереса, в среднем, первый работает минимум в 3 раза быстрее второго, а иначе не стал бы его здесь выставлять) 1

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 13:48
	Thinker, а как проводились тестирования? 0

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 14:15
	ValeryS, там выше есть уже этот алгоритм) 0

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 14:24
	ValeryS, #43 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	31.10.2012, 14:59 [ТС]
	Catstail, в криптографии нет ограничений. Там по принципу "чем сложнее, тем лучше". Поэтому ограничений на длину простых чисел тоже нет, чем длиннее, тем лучше. На этом базируется сложность вскрытия ассимметричных шифров, схем разделения секрета и т.д. Никакой массив не уместит столько простых чисел, чтобы перечислить все простые числа, которые могут быть использованы, например в RSA. 0

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 15:43
	Catstail, тем более чтение из огроменного массива будет занимать много времени, так как не все время же это будет находиться в ОЗУ. По этому это не вариант. Добавлено через 1 минуту Catstail, а прикинуть не сложно. Например взять 100 000 000 чисел - 100 000 000* 8 / 1024 /1024 = 7,6 мб , соответственно 1млрд - около 7,6 * 100 = 7600 мб 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	31.10.2012, 16:19 [ТС]
	AEXks, немного не то. Количество простых чисел от 2 до n примерно равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n}{\ln n}$ поэтому при n = 100 000 000 нужно примерно 45 мб., при n = 1 000 000 000 нужно 390 мб. и т.д. 0

@AEXks 24 / 3 / 0 Регистрация: 28.10.2012 Сообщений: 35
	31.10.2012, 23:00
	Thinker, столкнулся с некоторыми проблемами при реализации длинного деления по модулю. 1) почему то битовые операции работают только с 32х разрядными числами и не хотят сдвигать на 32 33 и выше. 2) как делить по модулю на составное число (реализовал только массив на uint) 0