Простые числа
Простое число - это число, которое делится только на 1 и на само себя. 1 не считается простым числом. Поэтому, любое простое число имеет только 2 делителя.
Используя оптимальный алгоритм подсчета числа делителей, можно сказать, что просто число не имеет делителей на промежутке от 2 до
\(\sqrt n\). Таким образом, достаточно перебрать возможные делители на диапазоне
\([2; \sqrt n ]\) и если на этом диапазоне нет делителей, то их не будет и на диапазоне
\([ \sqrt n + 1; n -1]\).
Фрагмент программы, который выводит на экран информацию о том, простое число
n или составное будет выглядеть так:
|
C++
|
Python |
Pascal |
int k = 0, i = 2;
while (i * i <= n)
{
if (n % i == 0)
{
k++;
break;
}
i += 1;
}
if (k == 0)
cout << "Число простое";
else
cout << "Число составное";
|
k = 0
i = 2
while i * i <=n:
if n % i == 0:
k += 1
break
i += 1
if k == 0:
print("Число простое")
else:
print("Число составное").
|
k := 0;
i := 2;
while i * i <= n do
begin
if n mod i = 0 then
begin
k := k + 1;
break;
end;
i := i + 1;
end;
if k = 0 then
write('Число простое')
else
write('Число составное');
|