сократить время выполнения

Question

как можно оптимизировать код, чтобы время выполнения стало меньше.

Сама задача: Дано натуральное число n. Найдите количество упорядоченных пар натуральных чисел (i, j) таких, что i ⋅ j =n, и наибольший общий делитель чисел i и j равен 1.

n=int(input())
k=0
def nod(i,j):
    while (i != j):
                if (i > j):
                    i=i - j
                else:
                    j = j - i
    return i
for i in range(n+1):
    for j in range (n+1):
        if i*j==n:
            if nod(i,j)==1:
                k+=1

print (k)

Answer 1

можно поменять последний цикл

for i in range(1, n + 1):
    if n % i == 0:
        j = n // i

Answer 2

""" 
Дано натуральное число n.
Найдите количество упорядоченных пар натуральных чисел (i, j) таких, что i*j=n, 
и наибольший общий делитель чисел i и j равен 1
"""

from math import sqrt, gcd;

def solve(n):
    k = 0
    for i in range(1, int(sqrt(n))+1): # не паримся с округлением корня, ведь i*i = n нас не интересует
        if n % i == 0:
            j = n // i
            if gcd(i, j) == 1:
                # print(f'{i}*{j}')
                k += 1
    return k

assert solve(12) == 2 # 1*12, 3*4
assert solve(30030) == 32
assert solve(510510) == 64

_{Не исключено, что я неверно понимаю термин «упорядоченных пар».

Тогда результат, скорее всего, нужно просто умножить на 2.}

БЛОГ НА HUSL

сократить время выполнения

Ответы (2 шт):