Alien Invasion II

'''

                            Online Python Compiler.
                Code, Compile, Run and Debug python program online.
Write your code in this editor and press "Run" button to execute it.

'''

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

    if cnt == 1:
        return (i-1)
    
    return n
    


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

    i = 1

    n2 = Prime(n1)
    
    while (n2==n1):
        s = str(n)
        s1 = str(i)

        s = s1 + s

        n1 = int(s)

        n2 = Prime(n1)

        i += 1

    print(n1)
    print(n2, end=' ')
    print(int(n1/n2))

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED