Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from math import log2
- def Sieve(limit=10**6):
- """Uses Sieve algorithm and stores a factor of each number!
- If isPrime[i] = 1, the number 'i' is prime."""
- isPrime = [1] * (limit + 1)
- isPrime[0] = isPrime[1] = 0
- for i in range(2, limit + 1):
- if isPrime[i] != 1:continue
- for j in range(i * i, limit + 1, i):
- if isPrime[j] == 1:isPrime[j] = i
- return isPrime
- def get_prime_factors(n, isPrime):
- """Returns prime factorisation of n."""
- if n < 2:
- return []
- result = []
- while isPrime[n] != 1:
- result += [isPrime[n]]
- n //= isPrime[n]
- result += [n]
- return result
- isPrime = Sieve(10**6)
- def solve(n):
- if n == 2:
- return 1
- minimumOnes, maximumOnes = n - 1 - int(log2(n)), n - 2
- for ones in range(minimumOnes, maximumOnes + 1):
- remaining = n - ones
- for product in range(n + 1, 2 * n + 1):
- req_sum = product - ones
- factors = get_prime_factors(req_sum, isPrime)
- for i in range(2, 100000):
- print(i, "->", solve(i))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement