PKU2262 Goldbach's Conjecture
用篩選法生成素數表prime[MAX]。。。
之前一直把最簡單的試除法當做篩選法來用,還認為效率很高， 然後這題就一直一直time limit exceed
1、試除法
用 n 除以 2-sqrt(n),有一個能除盡就不是素數，否則是素數。
時間復雜度：O(sqrt(n))
2、素數判斷法
這種方法是對上面方法的改進，上面方法是對 2-sqrt(n)之間的數進行判斷是否能除盡，而 因為有如下算術基本定理，可以減少判斷量。
算術基本定理：又稱為素數的唯一分解定理，即：每個大於 1 的自然數均可寫為素數的積， 而且這些素因子按大小排列之後，寫法僅有一種方式。
例如:6936 = 2^3×3×17^2，1200 = 2^4×3×5^2。 由算術基本定理知，任何合數都可分解為一些素數的乘積，所以判斷一個數能不能被 2-sqrt(n)之間的素數整除即可。
但是必須知道 2-sqrt(n)之間的所有素數。
3、篩選法
這種方法可以找出一定范圍內的所有的素數。
思路是，要求 10000 以內的所有素數，把 1-10000 這些數都列出來，1 不是素數，劃掉；2 是素數，所有 2 的倍數都不是素數，劃掉；取出下一個幸存的數，劃掉它的所有倍數；直到 所有幸存的數的倍數都被壞掉為止。
要找出 10000 以為的所有的素數，則需要一個大小為 10000 的數組,將其所有元素設置為未標記首先把 1 設置為標記，從 2 開始，標記所有是它 倍數的數，然後對下一個沒有標記的數進行標記它的倍數。當標記完成後，所有未標記的數 即為素數。
題意:
每次給一個偶數 n∈[ 6 , 1000000 )
輸出 ： n = a + b
要求: a+b=n, a和b都是奇素數，且b-a的值最大
先求出1000000內的所有素數，然後從3開始找滿足條件的a 和 b
注意 b=n-a
然後 b-a=n - 2*a
所以 a越大 b - a 越小
所以一旦找到滿足條件的 a和b 就 break
輸出 a b
[cpp]
#include<stdio.h>
bool prime[1000010];
int main()
{
int i,j,n;
for(i=3;i<=1000000;i+=2)
prime[i]=1;
for(i=3;i<500000;i++)
for(j=1;j<1000000/i;j++)
prime[i+j*i]=0;
while(scanf("%d",&n)&&n!=0)
{
for(i=3;i<=n/2;i+=2)
if(prime[i]&&prime[n-i])
break;
printf("%d = %d + %d\n",n,i,n-i);
}
return 0;
}
作者：dellaserss
