分拆素数和 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 42630 Accepted Submission(s): 18630
Problem Description 把一个偶数拆成两个不同素数的和，有几种拆法呢？
Input 输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。
Output 对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。
Sample Input
30 26 0
Sample Output
3 2
问题简述：哥德巴赫猜想说，大于2的偶数可以分解成两个素数之和。该问题求分解个数。
问题分析：解决本问题，首先用Eratosthenes筛选法求得必要的素数，然后用试探法求可分解的个数。
程序说明：
对于输入的偶数sum而言，如果能够分解成两个素数之和，其中一个必然小于或等于sum/2，基于这个原理进行分解计数，最后求出所有的组合。
#include <stdio.h> #include <math.h> // Eratosthenes筛选法 void sieveofe(int p[], int n) { int i, j; p[0] = 0; p[1] = 0; p[2] = 1; // 初始化 for(i=3; i<=n; i++) { p[i++] = 1; p[i] = 0; } int max = sqrt(n); for(i=3; i<=max; i++){ if(p[i]) { for(j=i+i; j < n; j+=i) //进行筛选 p[j]=0; } } } #define MAX 10000 int main(void) { int p[MAX+1]; int sum, count, i; sieveofe(p, MAX); for(;;) { scanf("%d", &sum); if(sum == 0) break; count = 0; for(i=2; i<=sum / 2; i++) { if(p[i] && p[sum-i]) if(i != sum-i) count++; } printf("%d\n", count); } return 0; }
