Alien Invasion II

import math
import sys


def Prime(n):
    cnt = 0
    for i in range(2, sys.maxsize):
        if i > math.sqrt(n) and cnt < 1:
            break
        if n % i == 0:
            cnt += 1

    return cnt < 1


def Factors(n):
    cnt = 0
    x = 2

    for i in range(2, sys.maxsize):
        if i > math.sqrt(n) and cnt < 1:
            break
        x+=1
        if n % i == 0:
            print(i)
            cnt+=1

    print(n/(x-1))

if __name__ == '__main__':
    n=int(input())
    n1 = n

    i = 1

    b = Prime(n1)

    while (b):
        s = str(n)
        s1 = str(i)

        s = s1 + s

        n1 = int(s)

        b = Prime(n1)

        i += 1

    print(n1)
    Factors(n1)

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED