Optimal algorithm
The number of checks for possible divisors can be significantly reduced if we take into account that each divisor
d has a number
n that does not exceed
\(\sqrt n\), there is "symmetrical" (pair) to it the divisor resulting from dividing
n by
d.
Example
For n = 30, it suffices to find the divisors 1, 2, 3, 5 (the integer part
\(\lfloor \sqrt {30} \rfloor = 5 \)). All other divisors can be obtained as follows:
30/1 = 30
30 / 2 = 15
30 / 3 = 10
30 / 5 = 6
The exception is a number that is an exact square. In this case, the
\(d= \sqrt{n}\) "symmetrical" he has no divisor.
Let's write a complete program using the loop operator with a precondition (
while) that counts the number of divisors of the number
n.
|
C++
|
|
#include <iostream>
using namespace std;
main()
{
intn;
cin>> n;
int k = 0, i = 1;
while (i * i < n)
{
if (n % i == 0)
{
k += 2; // given a symmetric divisor
}
i += 1; // move on to the next number
}
// check if the number n is an exact square;
// if n is an exact square, then the number of divisors
// increase by 1.
if (i * i == n)
{
k += 1;
}
cout << k;
}
|
| Python |
|
n = int(input())
k = 0
i = 1
while i * i < n:
if n % i == 0:
k += 2 # take into account the symmetrical divisor
i += 1 # move on to the next number
# check if the number n is an exact square;
# if n is an exact square, then the number of divisors
# increase by 1.
if i * i == n:
k += 1
print(k)
|
| Pascal |
|
var
n, i, k: integer;
begin
readln(n);
k := 0;
i := 1;
while i * i < n do
begin
if n mod i = 0 then
k := k + 2; // take into account the symmetrical divisor
i := i + 1; // move on to the next number
end;
// check if the number n is an exact square;
// if n is an exact square, then the number of divisors
// increase by 1.
if i * i = n then
k := k + 1;
write(k)
end.
|
Note
The loop statement checks for
i numbers less than the square root of
n. At the end of the loop, the variable
i can be equal to
\(\sqrt n\) (number
n is an exact square). In this case, this divisor must be taken into account.
You can also separately consider options when
n is an odd number and sort through only odd values
i.