解题思路

问题分析

题目要求对于给定的偶数 ( n )（( n \geq 4 )），统计满足 ( n = p_1 + p_2 ) 的素数对 ((p_1, p_2)) 的数量，其中 ( p_1 \leq p_2 )（避免重复计数）。核心步骤包括：

1. 预处理素数：使用筛法预先计算出范围内的所有素数，以便快速判断素数。
2. 枚举素数对：对于每个偶数 ( n )，枚举所有可能的素数对 ((p_1, p_2))，满足 ( p_1 \leq p_2 ) 且 ( p_1 + p_2 = n )。

算法步骤

1. 素数筛法预处理
   使用 埃拉托斯特尼筛法（Eratosthenes Sieve） 预处理出 ([0, \text{MAX}]) 范围内的所有素数，其中 (\text{MAX}) 设为 (2^{15} - 1 = 32767)（题目中 (n < 2^{15})，故最大可能的素数为 (n-2)，当 (n=32766) 时，最大素数为 (32765)，但 (32765) 不是素数，实际筛法范围可略大于此）。

   • 维护一个布尔数组 (\text{isprime})，标记每个数是否为素数；
   • 维护一个素数列表 (\text{su})，存储所有素数。

2. 枚举素数对
   对于每个输入的偶数 ( n )：

   • 从最小的素数开始枚举 ( p_1 )，使得 ( p_1 \leq n/2 ) 且 ( p_1 ) 是素数；
   • 计算对应的 ( p_2 = n - p_1 )，若 ( p_2 ) 是素数且 ( p_2 \geq p_1 )，则计数加一。

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX 50001//求MAX范围内的素数 
using namespace std;  
 
long long su[MAX],cnt;  
bool isprime[MAX];  
void prime()
{  
    cnt=1;  
    memset(isprime,1,sizeof(isprime)); 
    isprime[0]=isprime[1]=0;
    for(long long i=2;i<=MAX;i++)  
    {  
        if(isprime[i]) {
            su[cnt++]=i; 
        } 
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)  
        {  
            isprime[su[j]*i]=0;
        }  
    }  
}  
int main()
{
	prime();
	int n;
	int i,ans = 0; 
	while(scanf("%d",&n) && n ) {
		ans = 0;
		for( i= 3; i+i<=n; i+=2) {
			if(isprime[ i ] == 1 && isprime[n-i] == 1) {
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0 ;
 }