Alien Invasion II

import math
flag = 0

def isPrime(num):
    sqr = int(math.sqrt(num))+1
    for i in range(2, sqr+1):
        if num % i == 0:
            return i
    return -1

def bfs(num, depth, length):
    global flag
    if flag==1: 
        return
    if depth == 2:
        return
    for i in range(1,10):
        m = i*int(math.pow(10, length)) + num
        r = isPrime(m)
        if r != -1 and flag != 1:
            flag = 1
            print (m)
            print (r, int(m/r), sep=" ", end="")
            return

    for i in range(1,10):
        m = i*int(math.pow(10, length)) + num
        bfs(m, depth+1, length+1)

if __name__ == "__main__":
    n = int(input())
    length = 0
    r = isPrime(n)

    if r != -1:
        flag = 1
        print (n)
        print (r, int(n/r), sep=" ", end="")

    n_cp = n
    while (n_cp > 0):
        n_cp = n_cp // 10
        length += 1
    bfs(n, 0, length)
   

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED