Advertisement
mfgnik

Untitled

Jul 7th, 2020
1,517
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.65 KB | None | 0 0
  1. from copy import deepcopy
  2.  
  3.  
  4. def find_primes(sup):
  5.     cnt = 0
  6.     primes = [True] * (sup + 1)
  7.     primes[0] = primes[1] = False
  8.     for i in range(2, sup):
  9.         if not primes[i]:
  10.             continue
  11.         cnt += 1
  12.         for j in range(i * 2, sup + 1, i):
  13.             if primes[j]:
  14.                 primes[j] = False
  15.     return primes
  16.  
  17.  
  18. def factorize_all(sup):
  19.     primes = find_primes(sup)
  20.     factors = [None] * (sup + 1)
  21.     for number in range(2, sup + 1):
  22.         if primes[number]:
  23.             factors[number] = {number: 1}
  24.             continue
  25.         divisor = 2
  26.         while number % divisor:
  27.             divisor += 1
  28.         factors[number] = factors[number // divisor].copy()
  29.         factors[number][divisor] = factors[number].get(divisor, 0) + 1
  30.     return factors
  31.  
  32.  
  33. def calculate_divisor_sum(factor):
  34.     pair_amount = 1
  35.     for primes, degree in factor.items():
  36.         pair_amount *= (primes ** (degree + 1) - 1) // (primes - 1)
  37.     return pair_amount
  38.  
  39.  
  40. start, end = map(int, input().split())
  41. factors = factorize_all(end + 1)
  42. divisor_sums = {}
  43. friend_numbers = []
  44. for number in range(start, end + 1):
  45.     divisor_sum = calculate_divisor_sum(factors[number])
  46.     if divisor_sum not in divisor_sums:
  47.         divisor_sums[divisor_sum] = {divisor_sum - number}
  48.     elif number in divisor_sums[divisor_sum]:
  49.         friend_numbers.append((divisor_sum - number, number))
  50.         divisor_sums.pop(divisor_sum)
  51.     else:
  52.         divisor_sums[divisor_sum].add(divisor_sum - number)
  53. friend_numbers.sort()
  54. if friend_numbers:
  55.     for first, second in friend_numbers:
  56.         print(first, second)
  57. else:
  58.     print("Absent")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement