Prime numbers
A prime number is a number that is only divisible by 1 and itself. 1 is not considered a prime number. Therefore, any prime number has only 2 divisors.
Using the optimal algorithm for counting the number of divisors, we can say that just a number has no divisors in the interval from 2 to
\(\sqrt n\). Thus, it is enough to enumerate possible divisors on the range
\([2; \sqrt n ]\) and if there are no divisors on this range, then there will be none and on a range
\([ \sqrt n + 1; n -1]\).
A program fragment that displays information about whether a prime number
n or a composite number will look like this:
|
C++
|
Python |
Pascal |
|
int k = 0, i = 2;
while (i * i <= n)
{
if (n % i == 0)
{
k++;
break;
}
i += 1;
}
if(k==0)
cout << "Prime number";
else
cout << "Composite number";
|
k = 0
i = 2
while i * i <=n:
if n % i == 0:
k += 1
break
i += 1
if k == 0:
print("Prime number")
else:
print("Composite number").
|
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('Prime number')
else
write('Composite number');
|