一行目に質問の数 T、続く T 行に偶数 n が一つずつ与えられる。
質問ごとに、n を二つの素数 p, q の和 n = p + q (p ≤ q) で表す方法の数を一行ずつ出力せよ。
p と q の順序を入れ替えただけのものは同じ方法とみなす（10 = 3 + 7 = 7 + 3 は一通り）。
p = q でもよい（6 = 3 + 3）。
1 は素数ではない。
4 4 6 10 100
1 1 2 6
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
質問が 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);}