题解 - [LightOJ 1259] Goldbach`s Conjecture

发表于 更新于 分类于 ， 本文字数： 62 阅读时长 ≈ 1 分钟

题目链接

简述题意

给定 \(n\), 统计满足如下条件的数对 \((a,b)\) 个数

  1. \(a,b\) 均为素数
  2. \(a+b=n\)
  3. \(a\leqslant b\)

代码

Show code

LightOJ_1259view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
const int N = 1e7 + 5, M = 1e6 + 5;
int pri[M], cnt_pri;
bool vis[N];
int main() {
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) pri[++cnt_pri] = i;
    for (int j = 1; j <= cnt_pri && pri[j] * i < N; ++j) {
      vis[pri[j] * i] = 1;
      if (!(i % pri[j])) break;
    }
  }
  int kase;
  scanf("%d", &kase);
  for (int cnt = 1, n, sum; cnt <= kase; ++cnt) {
    sum = 0;
    scanf("%d", &n);
    for (int i = 1; pri[i] <= n / 2; ++i) sum += !vis[n - pri[i]];
    printf("Case %d: %d\n", cnt, sum);
  }
  return 0;
}