# your code goes here import math #zz=int((math.sqrt(100000)+1)) #zz=317 a=[0]*317 a[0]=a[1]=1 b=[] for i in range(2,317): if(a[i]==0): j=i+i b.append(i) while(j< 317): a[j]=1 j+=i la=len(b) for t in range(2,100000+1): print(str(t)+":",end=" ") x=0 p=int(math.sqrt(t)) while(x < la and b[x] <= p ): if(t % b[x] == 0): print(b[x],end=" ") while(t % b[x] == 0 ): t//=b[x] x+=1 if(t != 1): print(t) else: print()