基本解法和评论区一致,主要是解决超时的问题
{
int n;
scanf("%d",&n);
int i=2;
for(i=2;i*i<=n;i++)
{
//不用判断是否是质数,例如,如果i加到4,4一定不可以整除此时的n,如果可以整除,4作为合数,一定有2~4(开区间)之间的
//因子,而此区间的数都比4小,在i递增的过程中已经遍历过,把所有可以整除n的都筛选出来了,所以不需要判断是否是质数。
while(n%i==0)
{
printf("%d ",i);
n/=i;
}
}
if(n!=1){printf("%d",n);}
return 0;
}
1.不需要判断是否是质数
2.减小程序运行时间,缩小for循环的执行次数,改条件i<=n为i*i<=n,因为如果质数因子大于n的平方根,那么被因子整除后,结果比上一个质因子更小了。
但i*i<=n也会出现问题,就是当n成为质数本身的时候,不满足此条件,而此时仍然需要输出n,于是在for后补充一行,判断for循环是否拆分完了n,如果for循环已经
把n除到了1,那么已经拆分完毕,如果没有,那么剩余的最后一个质因子就是n本身
#include<stdio.h>
int main(void){
int n;
scanf("%d",&n);
int i=2;
for(i=2;i*i<=n;i++)
{
//不用判断是否是质数,例如,如果i加到4,4一定不可以整除此时的n,如果可以整除,4作为合数,一定有2~4(开区间)之间的
//因子,而此区间的数都比4小,在i递增的过程中已经遍历过,把所有可以整除n的都筛选出来了,所以不需要判断是否是质数。
while(n%i==0)
{
printf("%d ",i);
n/=i;
}
}
if(n!=1){printf("%d",n);}
return 0;
}