Alien Invasion II

import math
import sys


def Prime(n):
    cnt = 0

    i = 2
    while(i <= math.sqrt(n) and cnt < 1):
        if n % i == 0:
            cnt += 1

        i+=1

    return cnt < 1


def Factors(n):
    cnt = 0
   
    i = 2
    while(i <= math.sqrt(n) and cnt < 1):

        if n % i == 0:
            print(i)
            cnt+=1

        i+=1

    print(n/(i-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