Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p​1​​​k​1​​​​×p​2​​​k​2​​​​×⋯×p​m​​​k​m​​​​.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p​1​​^k​1​​*p​2​​^k​2​​*…*p​m​​^k​m​​, where p​i​​'s are prime factors of N in increasing order, and the exponent k​i​​ is the number of p​i​​ -- hence when there is only one p​i​​, k​i​​ is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

1 #include 
     
       2 #include 
      
        3 const int maxn = 100010; 4 bool isprime(int n) 5 {
   //判断n是否为素数 6     if (n == 1) 7         return false; 8     int sqr = (int)sqrt(1.0*n); 9     for (int i = 2; i <= sqr; i++)10     {11         if (n % i == 0)12             return false;13     }14     return true;15 }16 int prime[maxn], pNum = 0;17 void FindPrime()18 {
   //求素数表19     for (int i = 1; i < maxn; i++)20     {21         if (isprime(i) == true)22             prime[pNum++] = i;23     }24 }25 struct factor 26 {27     int x,cnt;//x为质因子，cnt为其个数28 }fac[10];29 30 int main()31 {32     FindPrime();//此句必须记得写33     int n, num = 0;//num为n的不同质因子的个数34     scanf("%d", &n);35     if (n == 1)36         printf("1=1");//特判1的情况37     else38     {39         printf("%d=", n);40         int sqr = (int)sqrt(1.0*n);//n的根号41         //枚举根号n以内的质因子42         for (int i = 0; i < pNum&&prime[i] <= sqr; i++)43         {44             if (n%prime[i] == 0)//如果prime[i]是n的因子45             {46                 fac[num].x = prime[i];//记录该因子47                 fac[num].cnt = 0;48                 while (n%prime[i] == 0)49                 {
   //计算出质因子prime[i]的个数50                     fac[num].cnt++;51                     n /= prime[i];52                 }53                 num++;//不同质因子个数加154             }55             if (n == 1)56                 break;//及时退出循环，节省点时间57         }58         if (n != 1)59         {
   //如果无法被根号n以内的质因子除尽60             fac[num].x = n;//那么一定有一个大于根号n的质因子61             fac[num++].cnt = 1;62         }63         //按格式输出结果64         for (int i = 0; i < num; i++)65         {66             if (i > 0)67                 printf("*");68             printf("%d", fac[i].x);69             if (fac[i].cnt > 1)70                 printf("^%d", fac[i].cnt);71         }72     }73     return 0;74 }