拆成两个素数之和
第一行给出询问数 T，接下来 T 行每行给出一个偶数 n。
对每个询问输出一行：把 n 写成两个素数之和 n = p + q (p ≤ q) 的方法数。
只交换 p 和 q 的顺序算同一种（10 = 3 + 7 = 7 + 3 只算一种）。
允许 p = q（6 = 3 + 3）。
1 不是素数。
- 输入
- 1 ≤ T ≤ 1,000，4 ≤ n ≤ 9,000，n 为偶数
- 输出
- T 行，每行一个方法数
4 4 6 10 100
1 1 2 6
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
有 1,000 个询问，对每个数试除判断素数会很慢。
先用埃拉托斯特尼筛法一次求出 9,000 以内的素数，然后每个询问把 p 从小到 n/2 全部试一遍，直接查表看 n - p 是否为素数。
各语言建筛的方式不同：Python [True] * (n + 1)，JavaScript/TypeScript new Array(n + 1).fill(true)，Java/C# new boolean[n + 1]/new bool[n + 1]（初始全为 false，当作「合数表」用就不必填充），C 用 static bool（只有全局/static 数组初始为 0，函数内的局部数组是垃圾值），C++ std::vector<bool>(n + 1, true)，Craykon 新列表(n + 1, 真)。
Craykon 的列表最多 10,000 项，所以 n 只到 9,000。
常见陷阱有三个：没有把 0 和 1 标为非素数（把 4 = 1 + 3 也算进去），写成 p < q 漏掉 6 = 3 + 3，让 p 一直跑到 n 把 3 + 7 和 7 + 3 算两次。
import sys LIMIT = 9000 # 에라토스테네스의 체: is_prime[k]는 k가 소수인지is_prime = [True] * (LIMIT + 1)is_prime[0] = is_prime[1] = Falsei = 2while i * i <= LIMIT: if is_prime[i]: for j in range(i * i, LIMIT + 1, i): is_prime[j] = False i += 1primes = [k for k in range(2, LIMIT + 1) if is_prime[k]] data = sys.stdin.read().split()t = int(data[0])out = []for n in map(int, data[1:1 + t]): count = 0 for p in primes: if p > n - p: # p <= q 인 것만 센다 break if is_prime[n - p]: count += 1 out.append(count)print("\n".join(map(str, out)))const LIMIT = 9000; // 에라토스테네스의 체: isPrime[k]는 k가 소수인지const isPrime = new Array(LIMIT + 1).fill(true);isPrime[0] = isPrime[1] = false;for (let i = 2; i * i <= LIMIT; i++) { if (!isPrime[i]) continue; for (let j = i * i; j <= LIMIT; j += i) isPrime[j] = false;}const primes = [];for (let k = 2; k <= LIMIT; k++) if (isPrime[k]) primes.push(k); const [t, ...ns] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = ns.slice(0, t).map((n) => { let count = 0; for (const p of primes) { if (p > n - p) break; // p <= q 인 것만 센다 if (isPrime[n - p]) count++; } return count;});console.log(out.join("\n"));import { readFileSync } from "node:fs"; const LIMIT = 9000; // 에라토스테네스의 체: isPrime[k]는 k가 소수인지const isPrime: boolean[] = new Array(LIMIT + 1).fill(true);isPrime[0] = isPrime[1] = false;for (let i = 2; i * i <= LIMIT; i++) { if (!isPrime[i]) continue; for (let j = i * i; j <= LIMIT; j += i) isPrime[j] = false;}const primes: number[] = [];for (let k = 2; k <= LIMIT; k++) if (isPrime[k]) primes.push(k); const [t, ...ns]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: number[] = ns.slice(0, t).map((n) => { let count = 0; for (const p of primes) { if (p > n - p) break; // p <= q 인 것만 센다 if (isPrime[n - p]) count++; } return count;});console.log(out.join("\n"));import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.ArrayList;import java.util.List; public class Main { public static void main(String[] args) throws IOException { final int LIMIT = 9000; boolean[] composite = new boolean[LIMIT + 1]; // 모두 false로 시작한다 composite[0] = composite[1] = true; for (int i = 2; i * i <= LIMIT; i++) { if (composite[i]) continue; for (int j = i * i; j <= LIMIT; j += i) composite[j] = true; } List<Integer> primes = new ArrayList<>(); for (int k = 2; k <= LIMIT; k++) if (!composite[k]) primes.add(k); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int q = 0; q < t; q++) { int n = Integer.parseInt(in.readLine().trim()); int count = 0; for (int p : primes) { if (p > n - p) break; // p <= q 인 것만 센다 if (!composite[n - p]) count++; } out.append(count).append('\n'); } System.out.print(out); }}using System;using System.Collections.Generic;using System.Text; class Program{ static void Main() { const int LIMIT = 9000; bool[] composite = new bool[LIMIT + 1]; // 모두 false로 시작한다 composite[0] = composite[1] = true; for (int i = 2; i * i <= LIMIT; i++) { if (composite[i]) continue; for (int j = i * i; j <= LIMIT; j += i) composite[j] = true; } var primes = new List<int>(); for (int k = 2; k <= LIMIT; k++) if (!composite[k]) primes.Add(k); int t = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int q = 0; q < t; q++) { int n = int.Parse(Console.ReadLine().Trim()); int count = 0; foreach (int p in primes) { if (p > n - p) break; // p <= q 인 것만 센다 if (!composite[n - p]) count++; } sb.Append(count).Append('\n'); } Console.Write(sb); }}#include <iostream>#include <vector> int main() { const int LIMIT = 9000; std::vector<bool> isPrime(LIMIT + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= LIMIT; i++) { if (!isPrime[i]) continue; for (int j = i * i; j <= LIMIT; j += i) isPrime[j] = false; } std::vector<int> primes; for (int k = 2; k <= LIMIT; k++) if (isPrime[k]) primes.push_back(k); int t, n; std::cin >> t; while (t-- > 0) { std::cin >> n; int count = 0; for (int p : primes) { if (p > n - p) break; // p <= q 인 것만 센다 if (isPrime[n - p]) count++; } std::cout << count << "\n"; }}#include <stdbool.h>#include <stdio.h> #define LIMIT 9000 static bool composite[LIMIT + 1]; /* static이라 모두 false로 시작한다 */static int primes[LIMIT]; int main(void) { int count_primes = 0; composite[0] = composite[1] = true; for (int i = 2; i * i <= LIMIT; i++) { if (composite[i]) continue; for (int j = i * i; j <= LIMIT; j += i) composite[j] = true; } for (int k = 2; k <= LIMIT; k++) if (!composite[k]) primes[count_primes++] = k; int t, n; scanf("%d", &t); while (t-- > 0) { scanf("%d", &n); int count = 0; for (int i = 0; i < count_primes && primes[i] <= n - primes[i]; i++) if (!composite[n - primes[i]]) count++; printf("%d\n", count); } return 0;}LIMIT = 9000; // 에라토스테네스의 체: isPrime[k]는 k가 소수인지isPrime = 新列表(LIMIT + 1, 真);isPrime[0] = 假;isPrime[1] = 假;循环 (i = 2; i * i <= LIMIT; i++){ 如果 (isPrime[i]) { 循环 (j = i * i; j <= LIMIT; j += i) { isPrime[j] = 假; } }}primes = [];循环 (k = 2; k <= LIMIT; k++){ 如果 (isPrime[k]) { primes.添加(k); }} t = 控制台.读行().转数字();循环 (q = 0; q < t; q++){ n = 控制台.读行().转数字(); count = 0; 遍历 (p 在 primes) { // p <= q 인 것만 센다 如果 (p > n - p) { 跳出; } 如果 (isPrime[n - p]) { count += 1; } } 控制台.输出(count);}