|
Проверка простого числа
Дано натуральное число
Необходимо определить, простое оно или нет
Простыми называют числа, имеющие только 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