소수 체모두 해 보기P0068

두 소수의 합으로 나누기

첫 줄에 질문 수 T가 주어지고, 다음 T줄에 짝수 n이 하나씩 주어진다.
질문마다 n을 두 소수 p, q의 합 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줄.
줄마다 방법의 수

예시 1 · stdin

stdout

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 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), 크레이콘 새목록(n + 1, 참).
크레이콘 목록은 10,000칸까지라 n을 9,000까지로 두었어요.
흔한 함정은 셋이에요: 0과 1을 소수 아님으로 표시하지 않기(4 = 1 + 3을 셈), p < q로 써서 6 = 3 + 3을 빠뜨리기, p를 n까지 돌려 3 + 7과 7 + 3을 두 번 세기.

Pythonmain.py · 27 줄

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)))

JavaScriptmain.js · 22 줄

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"));

TypeScriptmain.ts · 24 줄

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"));

JavaMain.java · 33 줄

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);    }}

C#Main.cs · 35 줄

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);    }}

C++main.cpp · 27 줄

#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";    }}

Cmain.c · 29 줄

#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;}

Craykonmain.cray · 44 줄

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);}