Pasted

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))