Optimizing the algorithm for finding divisors of a number
It takes a lot of time to iterate over all numbers from 1 to N and check each number for a multiplicity with a large
N value.
However, it is easy to verify that there are no divisors of the number
N in the interval
\([N/2+1; N -1]\) . Thus, we can reduce the number of checks by almost half.
|
C++
|
Python |
Pascal |
|
for(int i = 1; i <= n/2; i++)
if ( n % i == 0 )
{
...
}
|
for i in range(1, n//2 + 1):
if n % i == 0:
...
|
for i:=1 to n div 2+1 do
if( n mod i =0) then
...
|
You can also take into account the fact that an odd number of even divisors cannot have and iterate over the divisors of an odd number with a step of 2.
|
C++
|
|
if (n % 2 == 0)
{
for(int i = 1; i <= n/2; i++)
if ( n % i == 0 )
{
...
}
}
else
{
for(int i = 1; i <= n/3; i = i + 2)
if ( n % i == 0 )
{
...
}
}
|
| Python |
|
if n % 2 == 0:
for i in range(1, n//2 + 1):
if n % i == 0:
...
else:
for i in range(1, n//3 + 1, 2):
if n % i == 0:
...
|
| Pascal |
|
if n mod 2 = 0 then
for i:=1 to n div 2+1 do
begin
if n mod i = 0 then
// ...
end
else
i := 1;
while (i <= n div 3) do
begin
if n mod i = 0 then
// ...
i := i + 2;
end;
|