首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

跪求大神指导

2013-12-26 
跪求大神指点题目描述:[001]质因数分解 [EASY]Time Limit: 1000 msMemory Limit: 65536 KBTotal Submit: 9

跪求大神指点
题目描述:

[001]质因数分解 [EASY]
Time Limit: 1000 ms     Memory Limit: 65536 KB
Total Submit: 934     Accepted: 309 

Description
找出输入整数的所有质因数(包括重复质因数),并按从小到大的顺序依次输出。



Input
输入一组待分解整数,每个整数k占一行。
保证所有的输入数字1 <= k < 2^21 



Output
输出每个输入整数的所有质因数(按因子从小到大的顺序输出),质因数之间用空格隔开。

(每个数后边跟个空格就行,结果只有一个数的时候也跟个空格)

Sample Input
4
7
12



Sample Output
2 2 

2 2 3 


下面是我写的代码:


#include<iostream>
using namespace std;
void fun(int n)
{
int i=2;
if(n==1)
{
cout<<1<<" ";
}
while(n>0)
{
if(n%i!=0)
{
i++;
}
else
{
cout<<i<<" ";
n=n/i;
i=2;
}
}
cout<<endl;
}
int main()
{
int n;
while(cin>>n)
{
fun(n);
}
return 0;
}

但是提交之后总是显示
Time Limit Exceed错误  
有谁知道的 帮下忙啦 小弟第一次发帖 求关照 谢谢
[解决办法]
时间超时了, 你看下你的K 多大,你用辗转相除法在对大数求质数时,太耗时了
[解决办法]
除了fun中的循环代码(条件判别和else语句段)中的问题外,lz思路的还是稍微有点问题的:
尽管除数递增的思路在这种规模的数据下不算坏,但是如果N是一个接近于2^21的素数是不是就差一点了,给lz个思路(当然,肯定还有更好的方法):
(1)因为N <= 2^21,所以必然有N的质因数 < 2^11(如果N有质因数的话)
(2)先找出 < 2^11内所有的质数(不用担心,lz可以搜下素数筛选法,上界2048还是相当快的)
(3)让N试着除以这些质数来分解N

热点排行