方法一：《算法笔记》以及《王道机试指南》都是先取出sqrt(n)范围内的质数，然后遍历整除，求得相关质因数。

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 bool b[10000000]={0};
 5 int a[10000000];
 6 int main(){
 7     long long n;
 8     while(scanf("%lld",&n)!=EOF){
 9         int sqr=(int)sqrt(n);
10         int k=0;
11         for(int i=2;i<=sqr;i++){
12             if(b[i]==false){
13                 b[i]=true;
14                 a[k++]=i;
15                 for(int j=i+i;j<=sqr;j+=i){
16                     b[j]=true;
17                 }
18             }
19         }
20         for(int i=0;i<k;i++){
21             while(n%a[i]==0){
22                 printf("%d ",a[i]);
23                 n=n/a[i];
24             }
25         }
26         if(n!=1){
27             printf("%d ",n);
28         }
29     }
30 }

方法二：方法绝妙，参看代码，一开始无法理解为什么不需要判断后面的是不是素数，其实一开始整除2，就将所有相关的倍数除尽了。

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4     long n;
 5     while(cin>>n){
 6         for(int i=2;i<=n;i++){
 7             while(n%i==0){
 8                 cout<<i<<' ';
 9                 n/=i;
10             }
11         }
12     }
13 }