Hdu 4715 Difference Between Primes (2013网络赛 warm up) & LightOJ 1259 Goldbach`s Conjecture(素数和差)

川长思鸟来 2022-10-31 13:34 90阅读 0赞

和以前做过的一题很像，于是没细想就忽略了n==2这种情况。。。。以后不能再手残贡献WA了。。

**Hdu 4715 Difference Between Primes**

题意：一个偶数表示为两素数之差。

思路：猜想是正确的，所以不用考虑不存在的情况。

#include <cstdio>  
    #include <algorithm>
    using namespace std;
    
    const int N=10000007;
    
    bool visit[N];
    int prime[664600],np=0;
    
    void Prime () //素数打表prime数组从1开始
    {  
        visit[1]=true;
        for (int i=2;i<N;i++) if (!visit[i])
        {
            prime[++np]=i;  
            for (int j=i+i;j<N;j+=i)  
                visit[j]=true;  
        }  
    } 
    
    int main ()
    {  
        Prime ();
        int T,n;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
            scanf("%d",&n);
            int ans=0;
            if (n==2)
            {
                printf("5 3\n");
                continue;
            }
            int tmp = lower_bound(prime+1,prime+np+1,n)-prime;//按从小到大,最少能插入数组point的哪个位置
            for (int i=tmp;i<=np;i++) 
                if (visit[prime[i]-n]==false)
    			{
                    printf("%d %d\n",prime[i],prime[i]-n);
                    break;
    			}
        }  
        return 0;  
    }

**LightOJ 1259 Goldbach\`s Conjecture**

#include <cstdio>  
    
    const int N=10000007;
    
    bool visit[N];   //开成int爆内存……
    int prime[664600],np=1;
    
    void Prime ()           //素数打表prime数组从1开始  
    {  
        for (int i=2;i<N;i++) if (!visit[i])
        {
            prime[++np]=i;  
            for (int j=i+i;j<N;j+=i)  
                visit[j]=true;  
        }  
    } 
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n;
    	scanf("%d",&T);
    	Prime ();
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d",&n);
    		int ans=0;
    		for (int i=1; i<=np && prime[i]<=n/2; i++)
    			if (visit[n-prime[i]]==false)  // && vist[i]==false
    				ans++;
    		printf("Case %d: %d\n",Cas,ans);  
    	}  
    	return 0;  
    }  
    
    /*
    5
    5000010
    5000012
    5000014
    5000016
    10000000
    
    Output
    Case 1: 42737
    Case 2: 15856
    Case 3: 16375
    Case 4: 40308
    Case 5: 38807
    */