PKU2262 Goldbach's Conjecture 数论-素数

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

补充：软件开发 , C++ ,