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

bnVtYmVyID0gNjAwODUxNDc1MTQzCgpkZWYgZ2V0X3BfbWF4KG51bWJlciwgY3VycmVudF9wX21heCk6CiAgICAjIGluIHRoaXMgY2FzZSBudW1iZXIgaXMgYSBwcmltZSBudW1iZXIKICAgIGlmIG51bWJlciA8PSAzIG9yIGN1cnJlbnRfcF9tYXggKiogMiA+IG51bWJlcjoKICAgICAgICByZXR1cm4gbnVtYmVyCgogICAgIyBzcGVjaWFsIGNhc2UgZm9yIDIKICAgIGlmIGN1cnJlbnRfcF9tYXggPD0gMiBhbmQgbnVtYmVyICUgMiA9PSAwOgogICAgICAgIHJldHVybiBnZXRfcF9tYXgobnVtYmVyLy8yLCAyKQogICAgZWxzZToKICAgICAgICBzcSA9IGludChudW1iZXIqKjAuNSkKICAgICAgICBmb3IgaSBpbiByYW5nZShtYXgoMywgY3VycmVudF9wX21heCksIHNxICsgMSwgMik6CiAgICAgICAgICAgIGlmIG51bWJlciAlIGkgPT0gMDoKICAgICAgICAgICAgICAgIHJldHVybiBnZXRfcF9tYXgobnVtYmVyLy9pLCBpKQoKICAgICAgICAjIG1lYXNuICdudW1iZXInIGlzIGEgcHJpbWUKICAgICAgICByZXR1cm4gbnVtYmVyCgp0ZXN0X2Nhc2VzID0gWzEsIDIsIDMsIDQsIDUsIDgsIDksIDEwLCAyMDQ3LCAyMDQ4LCAyMDQ5LCA5OTcqOTk3LTEsIDk5Nyo5OTcsIDk5Nyo5OTcrMSwgbnVtYmVyXQoKZm9yIG51bSBpbiB0ZXN0X2Nhc2VzOgogICAgcHJpbnQobnVtLCBnZXRfcF9tYXgobnVtLCAxKSkKCg==