Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from copy import deepcopy
- def find_primes(sup):
- cnt = 0
- primes = [True] * (sup + 1)
- primes[0] = primes[1] = False
- for i in range(2, sup):
- if not primes[i]:
- continue
- cnt += 1
- for j in range(i * 2, sup + 1, i):
- if primes[j]:
- primes[j] = False
- return primes
- def factorize_all(sup):
- primes = find_primes(sup)
- factors = [None] * (sup + 1)
- for number in range(2, sup + 1):
- if primes[number]:
- factors[number] = {number: 1}
- continue
- divisor = 2
- while number % divisor:
- divisor += 1
- factors[number] = factors[number // divisor].copy()
- factors[number][divisor] = factors[number].get(divisor, 0) + 1
- return factors
- def calculate_divisor_sum(factor):
- pair_amount = 1
- for primes, degree in factor.items():
- pair_amount *= (primes ** (degree + 1) - 1) // (primes - 1)
- return pair_amount
- start, end = map(int, input().split())
- factors = factorize_all(end + 1)
- divisor_sums = {}
- friend_numbers = []
- for number in range(start, end + 1):
- divisor_sum = calculate_divisor_sum(factors[number])
- if divisor_sum not in divisor_sums:
- divisor_sums[divisor_sum] = {divisor_sum - number}
- elif number in divisor_sums[divisor_sum]:
- friend_numbers.append((divisor_sum - number, number))
- divisor_sums.pop(divisor_sum)
- else:
- divisor_sums[divisor_sum].add(divisor_sum - number)
- friend_numbers.sort()
- if friend_numbers:
- for first, second in friend_numbers:
- print(first, second)
- else:
- print("Absent")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement