Нахождение делителей числа?

Question

[alex_643]

Здравствуйте! Есть алгоритм факторизации(слышал что через него можно найти делители числа):

def Factor(n):
    Ans = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            Ans.append(d)
            n //= d
        else:
            d += 1
    if n > 1:
        Ans.append(n)
    return Ans

короче нужен эффективный алгоритм нахождения количества делителей числа. подскажите как это сделать?

Comments

[Матвей Истомин]

Эффективный по памяти или по времени?
Подробнее в Википедии

[alex_643]

Матвей Истомин, по времени

Answer 1

[Nick]

Здравствуйте!Есть идеи для такого алгоритма,можно идти до корня числа и проверять делится ли число,если делится - то сразу добавляем 2(т.к если 24 кратно 4,то оно и кратно 24/4),надо только проверить,если делитель * делитель не равно числу.
Вот реализация
while

def fact(a):
  i = 1
  o = 0
  while i * i <= a:
     if a % i == 0 and i * i != a: o += 2
     elif a % i == 0 and i * i == a: o += 1
     i += 1
  return o

Answer 2

[baknaryn]

n=int(input("n="))
flag=True
m=[]
i=2

while flag:
     if n%i==0:
            m.append(i)
            m.append(n//i)
     
     if n//i==i+1:
             flag=False
     i+=1
print(m)

Если рассмотреть число 58, то сразу находим два делителя 2 и 28, и т.д.