Description
任意一个正整数可以分解成唯一的质因数的乘积，给出正整数，请计算出它的质因数分解式。

输入

每行一个正整数2<=n<=10^8。

输出

每行输出一个对应结果。使用”^”表示幂，”*”表示乘，质因子应该按从小到大的顺序输出,如果某一个质因子只有一次，那么就不要输出它的幂。

 

Sample Input

2

6

36

 

Sample Output

2

2*3

2^2*3^2
 
#include<stdio.h>
#include<math.h>
int main()
 {
  int n,i,j,m,k;
    while ((scanf("%d",&n)!=EOF))
{           k=1;

          for(i=2;i<=sqrt(n);i++)
          {
            j=0;
            if(n%i==0)
            {if(k)k=0;
            else printf("*");
             printf("%ld",i);
            while(n%i==0){
                    j++;n/=i;}
            if(j>1)printf("^%d",j);
            }
          }
            if(n>1)
            if(k)printf("%d",n);
                else printf("*%d",n);
            printf("\n");
}
  return 0;
}

我的是这样的，超时，能指导一下吗？谢谢

优化算法

先把10^4以内质数存储,然后查表做质因数分解

代码不排版，不多说了
i<=sqrt(n) 也蛮令人佩服的，开根号是到初中才学的内容吧，就这么看不起小学的知识 i*i<=n

我把那个改了就过了，另外我们以前没学，现在才学的，算是从零开始。谢谢大神指点。i*i<=n

回复错了，我自醉。

我把那个改了就过了，另外我们以前没学，现在才学的，算是从零开始。谢谢大神指点。i*i<=n

大神我想了想你的算法。是用预处理吧。然后怎么处理了？

编译器出了问题，说一下思路
# include <stdio.h>
int main(void)
{

printf("请输入需要分解的数字");

printf ("请输入要分解的正整数\n")；
int i;
scanf ("%d", &i);
int j;


for (j=2;j<=i; ++j);//唯一不确定的是能否按照循环内的i=i/j 更新变量，进而缩小i范围，这一处请高手们指教！！（梯柱应该能看懂思路）
    do

    {    if (i%j!=0)
        break;
        i=i/j;
   
        printf ("d%",j);//怎么转换成字符输出就不知道了，新手一枚~~printf的话会输出质因数序
   
    }while(1);
return 0;
}

[此贴子已经被作者于2015-10-23 01:50编辑过]

#define MAX  10000

bool sa[MAX + 1] = { false };

void InitArray()
{
    for (size_t i = 2;i <= MAX;sa[i++] = true);
    for (size_t i = 2;i * 2 <= MAX;i++)  if (sa[i])
    for (size_t j = i + i;j <= MAX;sa[j] = false, j += i);
}