Оптимальный алгоритм
Количество проверок возможных делителей можно существенно сократить, если учесть, что у каждого делителя
d числа
n, не превышающего
\(\sqrt n\), есть "симметричный" (парный) ему делитель, получающийся в результате деления
n на
d.
Пример
Для n = 30 достаточно найти делители 1, 2, 3, 5 (целая часть
\(\lfloor \sqrt {30} \rfloor = 5 \)). Все остальные делители можно получить следующим образом:
30 / 1 = 30
30 / 2 = 15
30 / 3 = 10
30 / 5 = 6
Исключением является число, которое является точным квадратом. В этом случае у делителя
\(d= \sqrt{n}\) "симметричного" ему делителя нет.
Напишем полностью программy, использующую оператор цикла с предусловием (
while), которая подсчитывает количество делитей числа
n.
|
C++
|
#include <iostream>
using namespace std;
main()
{
int n;
cin >> n;
int k = 0, i = 1;
while (i * i < n)
{
if (n % i == 0)
{
k += 2; // учитывая симметричный делитель
}
i += 1; // переходим к следующему числу
}
// проверяем, является ли число n точным квадратом;
// если n является точным квадратом, то количество делителей
// увеличиваем на 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 # учитываем симметричный делитель
i += 1 # переходим к следующему числа
# проверяем, является ли число n точным квадратом;
# если n является точным квадратом, то количество делителей
# увеличиваем на 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; // учитываем симметричный делитель
i := i + 1; // переходим к следующему числа
end;
// проверяем, является ли число n точным квадратом;
// если n является точным квадратом, то количество делителей
// увеличиваем на 1.
if i * i = n then
k := k + 1;
write(k)
end.
|
Примечание
В операторе цикла проверяются числа
i, меньшие квадратного корня из
n. После окончания работы цикла переменная
i может быть равна
\(\sqrt n\) (число
n является точным квадратом). В этом случае необходимо учесть этот делитель.
Также можно отдельно рассматривать варианты, когда
n - нечетное число и перебирать только нечетные значения
i.