Всем здравствуйте! Есть код для решения задачи, но он работает слишком медленно. Нужно уложится в 1 секунду, а программа работает на ~1.1 секунду. Возможно, нужно как-то по-другому решить задачу, но не понимаю, как. Помогите, пожалуйста.
Условие задачи:
Дано натуральное число 𝑛
. Подсчитайте количество таких пар чисел (𝑎
и 𝑏
), что: 𝑎
и 𝑏
— делители 𝑛
; 𝑎 < 𝑏
; 𝑎
и 𝑏
— взаимно простые; 𝑎𝑏 ≤ 𝑛
.
Выходные данные:
Вводится натуральное число 𝑛 ≤ 10**8
.
Выходные данные:
Выведите количество таких пар.
Код:
from math import gcd
def full_factorization(n):
p = []
d = 2
while d * d <= n:
while n % d == 0:
p.append(d)
n //= d
d += 1
if n > 1:
p.append(n)
return p
def dividers(n):
p = full_factorization(n)
divs = []
for i in range(1, n + 1):
if n%i == 0:
divs.append(i)
return divs
def main(n):
used = []
number = 0
div = dividers(n)
for a in div:
for b in div:
if a < b and (a,b) not in used and gcd(a,b) == 1 and a*b <= n:
number += 1
used += [(a, b), (b, a)]
return number
n = int(input())
print(main(int(input())))
n
на простые множители. Дальше работайте только с количествами каждого отдельного делителя. С учётом того, что разa
иb
взаимно просты, то наличие какого-то количества какого-то множителя у одного из чисел автоматом определяет нулевое их количество у другого.