@jinxonik / UniLecs #83

RevSumEquation.py

# Вычисление кол-ва "уравнений обратной суммы" 1/n=(1/x+1/y) для натуральных x и y через разложение на простые множители
# В данной функции перемножаются степени каждого множителя, умноженные на 2 и увеличенные на 1
# Например, 12250 = 2^1 * 5^3 * 7^2. Сами простые множители нас не интересуют, нас интересуют только их степени (1, 3, 2)
# Таким образом ответом будет (1*2+1) * (3*2+1) * (2*2+1) = 105
def RSEnum(n):
  i = 2
  # вычисляем простые числа
  result = 1
  while i*i <= n:
    k = 1
    while n % i == 0:
      k += 2
      n //= i
    # умножаем результат на (степень_найденного_простого_числа * 2 + 1)
    result *= k
    i += 1
  if n > 1: result *= 3  # здесь степень будет всегда = 1, а значит 1*2+1 = 3
  return result

for n in (1,2,3,7,10,256,600,4321,12250,777777,1000000,999999999):
  print('For {} found {} solutions'.format(n, RSEnum(n)))