PYTHON Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x≤2∗109).
Входные данные
Вводится натуральное число x.
Выходные данные
Выведите единственное число - количество делителей числа x.
Примеры
Входные данные
32
Выходные данные
6
Я написал вот такой код, но написано, что превышено максимальное время работы программы:
x=int(input())
a=0
for b in range(1, x+1):
if x%b==0:
a=a+1
print(a)
Что я делаю не так?
Превышение максимального времени работы программы может быть связано с тем, что твой код перебирает все числа от 1 до x в поиске делителей. Это очень медленно для больших чисел.
Есть более оптимальный подход для подсчета количества делителей числа x. Давай изучим его.
Факторизация - процесс разложения числа на простые множители. Воспользуемся этим подходом для решения задачи.
1. Инициализируй переменную count в 1. В ней будем подсчитывать количество делителей.
2. Исследуй числа от 2 до √x. Если число i делит x, то добавим к переменной count 2: i и x/i, так как они являются парными делителями. Обрати внимание, что мы доходили только до √x, так как все числа, большие этой границы, уже содержатся в числах до √x.
3. Если x является полным квадратом (т.е. √x является натуральным числом), добавь 1 к переменной count.
4. Выведи значение переменной count.
С точки зрения времени выполнения, этот алгоритм более эффективен, так как перебирает всего √x чисел для поиска делителей.
Пример кода, решающего эту задачу:
import math
x = int(input())
count = 0
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0:
count += 2
if math.sqrt(x) == int(math.sqrt(x)):
count += 1
count += 2 # учитываем единицу и само число x как делители
print(count)
Теперь твоя программа должна работать корректно и подсчитывать количество натуральных делителей числа x.