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

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

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

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

29.09.2012, 21:35. Просмотров 49706. Ответов 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....

90
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 13:04 #46
Catstail, в этой теме рассматриваются числа уже больше чем 1000, а именно как минимум _int64, и для этих числе я решил задачу ( читайте выше) А щас надо попытаться сделать длинное деление по модулю

Добавлено через 5 минут
Thinker, сложность то будет немного другая , я бы сказал O(ln n) * 2 так как вы в проверке еще сдвиги делаете и еще проверок в два раза больше - в цикле и для того чтобы суммировать.. в общем надо уже на практике заменять разные реализации и при прочих равных условиях посмотреть что получится) ок. Попробую
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 13:09  [ТС] #47
AEXks,
O(ln n)*2 = O(ln n)
алгоритмы я протестировал для интереса, в среднем, первый работает минимум в 3 раза быстрее второго, а иначе не стал бы его здесь выставлять)
1
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,189
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 прикинь размер массива
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 13:48 #49
Thinker, а как проводились тестирования?
0
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,189
31.10.2012, 13:49 #50
Цитата Сообщение от AEXks Посмотреть сообщение
Но тогда чем больше ширина сдвига, тем больше нужно сделать сдвигов для маленьких чисел.
не будет сдвигов по твоему алгоритму
Цитата Сообщение от AEXks Посмотреть сообщение
for( ; dig >= 0xFF; )
число меньше чем 0xFF в цикл не входим

если скрестить мой второй алгоритм (My1Algor) и твой (AEXksHiAlgor) то для _int64 можно наверное вообще без циклов обойтись, только проверки(if)
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 13:56  [ТС] #51
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а как проводились тестирования?
просто прогнал все числа от 2 до 100 000 000 на время) ну и, конечно, теоретически видно из сложности алгоритмов.
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 14:15 #52
ValeryS, там выше есть уже этот алгоритм)
0
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,189
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, там выше есть уже этот алгоритм)
ты сейчас про какой??(хоть номер поста указывай)
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 14:24 #54
ValeryS, #43
0
Catstail
Модератор
22833 / 11199 / 1812
Регистрация: 12.02.2012
Сообщений: 18,437
31.10.2012, 14:48 #55
Цитата Сообщение от ValeryS Посмотреть сообщение
вообще то здесь речь шла о числах как минимум 2 в 64 прикинь размер массива
- а это так просто, "прикинуть"? И потом, если простые числа нужны для каких-либо приложений, их диапазон "по-любому" ограничен. Поэтому целесообразно один раз массив сформировать, а потом пользоваться.
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 14:59  [ТС] #56
Catstail, в криптографии нет ограничений. Там по принципу "чем сложнее, тем лучше". Поэтому ограничений на длину простых чисел тоже нет, чем длиннее, тем лучше. На этом базируется сложность вскрытия ассимметричных шифров, схем разделения секрета и т.д. Никакой массив не уместит столько простых чисел, чтобы перечислить все простые числа, которые могут быть использованы, например в RSA.
0
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 мб
0
Thinker
Эксперт С++
4228 / 2202 / 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 мб. и т.д.
0
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
31.10.2012, 23:00 #59
Thinker, столкнулся с некоторыми проблемами при реализации длинного деления по модулю.
1) почему то битовые операции работают только с 32х разрядными числами и не хотят сдвигать на 32 33 и выше.
2) как делить по модулю на составное число (реализовал только массив на uint)
0
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,189
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
от чего ушли к тому пришли
0
01.11.2012, 08:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2012, 08:39
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Опции темы

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