number = 600851475143

def get_p_max(number, current_p_max):
    # in this case number is a prime number
    if number <= 3 or current_p_max ** 2 > number:
        return number

    # special case for 2
    if current_p_max <= 2 and number % 2 == 0:
        return get_p_max(number//2, 2)
    else:
        sq = int(number**0.5)
        for i in range(max(3, current_p_max), sq + 1, 2):
            if number % i == 0:
                return get_p_max(number//i, i)

        # measn 'number' is a prime
        return number

test_cases = [1, 2, 3, 4, 5, 8, 9, 10, 2047, 2048, 2049, 997*997-1, 997*997, 997*997+1, number]

for num in test_cases:
    print(num, get_p_max(num, 1))