Проверка простого числа



Дано натуральное число
Необходимо определить, простое оно или нет

Простыми называют числа, имеющие только 2 положительных делителя (2, 3, 5, 11, 29).
Чтобы узнать простое данное число или нет достаточно перебрать все его делители и проверить, что их только два.

Асимптотика O(sqrt(n)).


Листинг С++

bool prime (int a)
{
   if (a == 2) return true;
   if (a < 3 || (a & 1) == 0) return false;
   int i, ii;
   for (i = 3, ii = 9; ii <= a; ii += (i << 2) + 4, ++++ i)
      if (a % i == 0)
         return false;
   return true;
}

14:09
03.02.2010


По всем вопросам обращаться: rumterg@gmail.com