#
naif(n)=if(n<4,print("prime"),\
        if(lift(Mod(n,2))==0,print("2*",n/2),\
        if(lift(Mod(n,3))==0,print("3*",n/3),\
        sq=sqrt(n);e=2;d=5;\
        while(d<sq,if(lift(Mod(n,d))==0,\
           dd=d;d=n,d=d+e;e=6-e));\
        if(d==n,print(dd,"*",n/dd),print("prime")\
        ))))