题解 | #质数因子#
质数因子
http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
编辑一下，看了别人的代码才醒悟过来。只要从2开始循环除，就可以保证每个因数都是质数了，就不用每个数都验证了。
唉，丢人。数论这块是完全不行啊。
实现本身不难，也不用排序，就是一直超时。只能优化算法。关键点在于，一是验证是否为质数时，循环到平方根即可，这个属于是数学知识了；二是当题目给出的是超巨大质数时的计算，加了个判定是否为质数，是的话直接输出的环节。
只能说果不其然，还真有个超巨大的素数。属于是勾心斗角了。
#include<stdio.h>
#include<math.h>
int judge(int a);
int main()
{
int input;
int x=2;
scanf("%d", &input);
while(input>1)
{
if(judge(input)==1)
{
printf("%d ", input);
break;
}
if((input%x)==0&&judge(x)==1)
{
while((input%x)==0)
{
printf("%d ", x);
input/=x;
}
x++;
}
else x++;
}
return 0;
}
int judge(int a)
{
int i;
for(i=2; i<(int)sqrt(a)+1; i++)
{
if((a%i==0)) return 0;
}
return 1;
}
投递华为等公司8个岗位 >
传音控股成长空间 169人发布