求一个数的分解

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<cmath>
 4 # include<cstring>
 5 
 6 using namespace std;
 7 
 8 # define MAX 123
 9 
10 int prime[MAX];
11 int ex[MAX];
12 int cnt;
13 
14 
15 void factor ( long long x )
16 {
17     cnt = 0;
18     int m = sqrt(x);
19     for ( int i = 2;i <= m;i++ )
20     {
21         if ( x%i==0 )
22         {
23             prime[++cnt] = i;
24             while ( x%i==0 )
25             {
26                 x/=i;
27                 ex[cnt]++;
28             }
29         }
30     }
31     if ( x > 1 )
32     {
33         prime[++cnt] = x;
34         ex[cnt] = 1;
35     }
36 }
37 
38 
39 int main(void)
40 {
41     long long n;
42     while ( cin>>n )
43     {
44         factor(n);
45         for ( int i = 1;i <= cnt;i++ )
46         {
47             printf("%d ",prime[i]);
48             printf("%d
",ex[i]);
49         }
50         memset(prime,0,sizeof(prime));
51         memset(ex,0,sizeof(ex));
52    }
53 
54     return 0;
55 }

　　这是把一个大数分解成为cnt个素数并且知道每个素数的次幂的常用代码，，对于做很多题目来说都是一个很快捷的做法。

就类似于判断素数，每次判断一个素数，如果他是素数的话，就把他除干净，然后边除边统计次幂.