跪求大神指导
跪求大神指点
题目描述：
[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
7
2 2 3
下面是我写的代码：
但是提交之后总是显示
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
题目描述：
[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
7
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