求一个数所有质因数

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define E  2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=2e5+10;
 25 
 26 int zhi[maxn];
 27 bool vis[maxn]={0};
 28 vector<int> st;
 29 int tot,s[100],t[100],g=0;
 30 vector<int>* vec;
 31 
 32 void build(int index,int value)
 33 {
 34     if (index==tot)
 35         vec->push_back(value);
 36     else
 37         build(index+1,value);
 38 
 39     int i;
 40     for (i=1;i<=t[index];i++)
 41     {
 42         value*=s[index];
 43         if (index==tot)
 44             vec->push_back(value);
 45         else
 46             build(index+1,value);
 47     }
 48 }
 49 
 50 void work(vector<int>* _vec,int v)
 51 {
 52     int i;
 53     tot=0;
 54     for (i=1;i<=g;i++)
 55         if (v%zhi[i]==0)
 56         {
 57             tot++;
 58             s[tot]=zhi[i];
 59             t[tot]=0;
 60             while (v%zhi[i]==0)
 61             {
 62                 v/=zhi[i];
 63                 t[tot]++;
 64             }
 65             if (v==1)
 66                 break;
 67         }
 68     if (v!=1)
 69     {
 70         tot++;
 71         s[tot]=v;
 72         t[tot]=1;
 73     }
 74 
 75     vec=_vec;
 76     vec->clear();
 77 
 78     if (tot==0) //v=1
 79         vec->push_back(1);
 80     else
 81         build(1,1);
 82 
 83     sort(vec->begin(),vec->end());
 84 
 85     for (vector<int>::iterator j=st.begin();j!=st.end();j++)
 86         printf("%d ",*j);
 87     printf("

");
 88 }
 89 
 90 void getzhi()
 91 {
 92     int i,j,k;
 93     int v=sqrt(3e10);
 94     for (i=2;i<=v;i++)
 95     {
 96         if (!vis[i])
 97         {
 98             g++;
 99             zhi[g]=i;
100         }
101         for (j=1;j<=g;j++)
102         {
103             k=i*zhi[j];
104             if (k>v)
105                 break;
106             vis[k]=1;
107             if (i%zhi[j]==0)
108                 break;
109         }
110     }
111 }
112 
113 
114 int main()
115 {
116     int v;
117     getzhi();
118     while (~scanf("%d",&v))
119     {
120         work(&st,v);
121     }
122     return 0;
123 }