Problem Description
把一个偶数拆成两个不同素数的和, 有几种拆法呢?
Input
输入包含一些正的偶数, 其值不会超过 10000, 个数不会超过 500, 若遇 0, 则结束
Output
对应每个偶数, 输出其拆成不同素数的个数, 每个结果占一行
- Sample Input
- 30 26 0
- Sample Output
- 3 2
- Source
2007 省赛集训队练习赛 (2)
自己写了一个素数打表的函数
- bool isPrime(int x)
- {
- for(int i = 2; i * i < x; i++)
- {
- if(x % i == 0) return false;
- }
- return x != 1;
- }
- void prime()
- {
- for(int i = 2; i < 10000; i++) {
- if(isPrime)
- {
- a[flag++] = i;
- }
- }
- }
提交的时候 WA, 后来发现它把 4, 25 这两个数也加在了素数表中
正确打表模板
- #include < stdio.h > int n,
- i,
- j,
- a[1000001],
- p[100000],
- t = 0;
- void main() {
- scanf("%d", &n);
- a[1] = 0;
- for (i = 2; i <= n; i++) a[i] = 1;
- for (i = 2; i <= n; i++) if (a[i]) {
- p[t++] = i; //i 即为被记录的素数
- for (j = i + i; j <= n; j += i) a[j] = 0; // 素数的倍数都标记为零
- }
- for (i = 0; i < t; i++) printf("%d%c", p[i], i < t - 1 ? : \n);
- }
埃氏筛法
- int prime[MAX_N];
- bool isPrime[MAX_N + 1];
- int sieve(int n) {
- int p = 0;
- for(int i = 0; i <= n; i++)
- isPrime[i] = true;
- isPrime[0] = isPrime[1] = false;
- for(int i = 2; i <= n; i++) {
- if(isPrime[i]) {
- prime[p++] = i;
- for(int j = 2 * i; j <= n; j += i) {
- isPrime = false;
- }
- }
- }
- return p;
- }
AC 代码
- #include<stdio.h>
- #include<math.h>
- int a[5000];
- int flag = 0;
- int prime(int n)
- {
- int i,q;
- q=(int)sqrt(n);
- for(i=0; (a[i]<=q && flag); i++)
- if(n%a[i]==0)
- return 0;
- return 1;
- }
- int main()
- {
- int n;
- for(int i=2; i<=10000; i++)
- if(prime(i))
- a[flag++]=i;
- while(~scanf("%d", &n) && n != 0)
- {
- int flag2;
- int num = 0;
- for(int i = 0; i < flag; i++)
- {
- if(a[i] >= n)
- {
- flag2 = i;
- }
- }
- //for(int i = 0; i < flag; i++)
- // printf("%d", a[i]);
- for(int i = flag2 - 1; i > 0; i--)
- {
- for(int j = 0; j < i; j++)
- {
- if((a[i] + a[j]) == n)
- num++;
- else if((a[i] + a[j]) > n)
- break;
- else if((a[i] + a[j]) < n)
- continue;
- }
- }
- printf("%d\n", num);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2516771.html