#!/usr/bin/python3

import math 

# https://math.stackexchange.com/questions/1039519/finding-prime-factors-by-taking-the-square-root
# DIY factoring functions, but for small numbers it is OK
def factor_helper(n):
    for i in range(2, int(math.ceil(math.sqrt(n)))+1):
        if n % i == 0:
            return i
    # this is prime
    return n

def factor(n):
    rt=[]
    while True:
        p=factor_helper(n)
        if p==1:
            break
        rt.append (p)
        n=n//p
    return rt

first_primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

smallest_result=-1
smallest_divisors=-1
smallest_solutions=-1

def try_(solutions_we_want, divisors_we_want):
    global smallest_result
    global smallest_divisors
    global smallest_solutions

    factors=factor(divisors_we_want)
    if max(factors)>100:
        # skip it, because we need small results anyway
        return

    factors=sorted(factors, reverse=True)

    rt=1
    for p, f in zip(first_primes, factors):
        rt*=p**(f-1)

    try:
        result=int(math.sqrt(rt))
    except OverflowError:
        # skip it, because we need small results anyway
        return

    print (divisors_we_want, result)
    if (smallest_result==-1) or (result<smallest_result):
        smallest_result=result
        smallest_divisors=divisors_we_want
        smallest_solutions=solutions_we_want

#for solutions_we_want in range(1000, 2000): # for PE 108
for solutions_we_want in range(4*10**6, 4*10**6+100000): # for PE 110
    divisors_we_want=(solutions_we_want*2)-1;
    try_ (solutions_we_want, divisors_we_want)

print (f"{smallest_result=}")
print (f"{smallest_solutions=}")
print (f"{smallest_divisors=}")