# your code goes here import math res=[] for i in range(2,100000): s=str(i)+": " for j in range(2,int(math.sqrt(100000))): if (i%j==0): s+=str(j)+" " while(i%j == 0): i//=j if(i != 1): res.append(s+str(i)) else: res.append(s) for _ in res: print(_)