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