欧拉计划3.找出一个合数的最大质数因子

由于数学太差了，来搞搞pe，先从水题做起。

题意：

13195的质数因子有5,7,13和29.

600851475143的最大质数因子是多少？

这里可以肯定的是：1.数字很大，绝对不能暴力。2.如果这是一到OJ题，那么我们的目的就是尽量缩小这个数，减少计算量。

我们都知道，任何一个合数都是可以由他的所有质因素相乘得到的，比如15=3*3*3*3*3,12=2*2*3，60=2*2*3*5.（这些数都是我随便想的），好的，我们先看一个比较小的数60，现在我们要找它的最大质因子，我们可以从最小的奇数开始枚举(当然要先枚举2这个特殊的质数，除此之外的偶数可能是质数吗？)，如果可以整除说明这个奇数是其因子之一，然后判断这个奇数如果是质数，那么它就是其中一个质因子。然后原数就可以除这个因子了，为了排除已经找到的因子，我们一直将它除这个数，直到不能整除，60/=2得30,30/=2得15，到此结束此因子，我们就找到了2这个质因子；同理，到3的时候15/=3得5，找到了3这个质因子；5/5=1，可以结束，5就是我们要找的最大质因子啦。如果是多测试的话一直频繁判断素数是不是有点不爽？所以我们可以打个素数表- -。还有一个优化就是这个素数不会超过sqrt(n)，可以减少循环次数，至于证明自己搜吧。

下面给出算欧拉计划的代码：

 1 #include<bits/stdc++.h>
 2 
 3 #define PAUSE system("pause");
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 typedef unsigned long long ull;
 9 
10 const int MAXN = 100000000;
11 int prime[MAXN],cnt_prime=0;
12 bool isprime[MAXN];
13 
14 inline void show(int *ary,int n)
15 {
16     for(int i=0;i<=n;i++)
17         printf("%d ",ary[i]);
18 }
19 
20 void GetPrime(int MAX)
21 {
22     memset(isprime,0,sizeof(isprime));
23     int m=(int)sqrt((double)MAX);
24 
25     for(int i=2;i<=m;i++)
26     {
27         if(!isprime[i])
28         {
29             for(int j=i*i;j<=MAX;j+=i)
30             {
31                 isprime[j]=1;
32             }
33         }
34     }
35 
36     cnt_prime=0;
37     for(int i=2;i<=MAX;i++)
38     {
39         if(!isprime[i])
40         {
41             prime[cnt_prime++]=i;
42         }
43     }
44 }
45 
46 int findit(ull num)
47 {
48     ull m = (int)sqrt(double(num));
49     ull lastf,f;
50     if((num&1)==0)
51     {
52         lastf = 2;
53         num>>=1;
54         while((num&1)==0)
55             num>>=1;
56     }
57     else
58         lastf = 1;
59 
60     f=3;
61     for(int i = 2; num > 1 && f < m; i++)
62     {
63         f = prime[i];
64         if(num % f == 0)
65         {
66             num /= f;
67             lastf = f;
68             while(num%f==0)
69                 num/=f;
70             m=(int)sqrt(double(num));
71         }
72     }
73 
74     if(num==1)
75         return lastf;
76     else
77         return num;
78 }
79 
80 int main()
81 {
82     double start, finish;
83     GetPrime(10000000);
84     start = clock();
85     cout<<findit(600851475143)<<endl;
86     finish = clock();
87     printf("%f sec",(finish - start) / CLOCKS_PER_SEC);
88 }

运行结果:

6857
0.001000 sec