Оптимизация алгоритма поиска делителей числа
Для перебора всех чисел от 1 до N и проверка каждого числа на кратность при большом значении
N занимает большое количество времени.
Однако легко убедиться, что в интервале
\([N/2+1; N -1]\) делителей числа
N нет. Таким образом, можем сократить количество проверок почти в два раза.
|
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
...
|
Можно также учесть тот факт, что у нечетного числа четных делителей быть не может и перебирать делители у нечетного числа с шагом 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;
|