Форум программистов, компьютерный форум, киберфорум
Thinker
Войти
Регистрация
Восстановить пароль
Оценить эту запись

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

Запись от Thinker размещена 10.07.2013 в 09:49

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

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм
Кликните здесь для просмотра всего текста
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;
}

В данном алгоритме из множества отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества , которые взаимно просты с 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;
}

Также проверку на простоту можно в одну строчку написать (для 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). Кратко и понятно, только толку от него почти никакого.
Размещено в Без категории
Показов 3408 Комментарии 0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru