자연수 x의 10진법 숫자를 뒤에서부터 읽은 수를 뒤(x)라 하자.
맨 앞에 오는 0은 버린다(120 → 21, 7 → 7).
x와 뒤(x)가 모두 소수이면 x를 '뒤집어도 소수'라 한다.
뒤(x)가 x와 같아도 된다.
그래서 2, 11, 101도 뒤집어도 소수다.
소수는 1과 자기 자신으로만 나누어떨어지는 1보다 큰 정수다.
1은 소수가 아니다.
첫 줄에 질문 수 q가, 다음 q줄에 질문마다 두 정수 a, b가 빈칸으로 나뉘어 주어진다.
질문마다 a 이상 b 이하인 수 가운데 뒤집어도 소수인 수의 개수를 한 줄에 출력하라.
3 1 10 10 20 100 199
4 3 12
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
질문이 많으니 에라토스테네스의 체로 9,999까지 소수 표를 한 번 만들어 두고 질문마다 표를 읽어요.
표는 0번부터 9,999번까지 10,000칸이에요.
크기를 9,999로 만들면 마지막 칸이 없어서 Python·Java·C#·크레이콘은 범위 밖 오류로 멈추고, C는 오류 없이 배열 밖을 읽어요.
만드는 법: Python [True] * (LIMIT + 1), JS·TS new Array(LIMIT + 1).fill(true), C# new bool[LIMIT + 1] 뒤에 Array.Fill, C++ std::vector<bool>(LIMIT + 1, true), 크레이콘 새목록(LIMIT + 1, 참).
Java boolean[]과 C의 static 배열은 처음에 모두 false라서, '합성수인가'로 거꾸로 적거나 2부터 true로 채워요.
0과 1은 처음에 소수가 아니라고 적어 둬요(1을 빼먹으면 1도 세요).
함정은 체의 크기예요.
질문의 b까지만 체를 만들면 13을 뒤집은 31처럼 b보다 큰 수가 소수인지 알 수 없어요.
뒤집은 수도 9,999를 넘지 않으니 늘 9,999까지 만들어요.
흔히 알려진 '에미르프'는 뒤집은 수가 자기와 달라야 하지만, 이 문제는 2, 11, 101처럼 같아도 세요.
구간은 b를 포함하니 x <= b까지 돌아요.
숫자를 뒤집을 때 JS·TS의 /와 크레이콘의 /는 소수까지 나누니 Math.floor(x / 10), 수학.몫(x, 10)을 써요.
LIMIT = 9999 # 뒤집은 수도 9,999를 넘지 않는다 # 에라토스테네스의 체: 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 += 1 def rev(x): r = 0 while x > 0: r = r * 10 + x % 10 x //= 10 return r good = [is_prime[x] and is_prime[rev(x)] for x in range(LIMIT + 1)] q = int(input())for _ in range(q): a, b = map(int, input().split()) print(sum(1 for x in range(a, b + 1) if good[x]))const LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다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;}function rev(x) { let r = 0; while (x > 0) { r = r * 10 + (x % 10); x = Math.floor(x / 10); // /는 소수까지 나눈다 } return r;}const good = isPrime.map((p, x) => p && isPrime[rev(x)]); const [q, ...nums] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];for (let k = 0; k < q; k++) { const a = nums[2 * k], b = nums[2 * k + 1]; let c = 0; for (let x = a; x <= b; x++) if (good[x]) c++; out.push(c);}console.log(out.join("\n"));import { readFileSync } from "node:fs";const LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다const isPrime: boolean[] = new Array<boolean>(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;}function rev(x: number): number { let r = 0; while (x > 0) { r = r * 10 + (x % 10); x = Math.floor(x / 10); // /는 소수까지 나눈다 } return r;}const good: boolean[] = isPrime.map((p, x) => p && isPrime[rev(x)]); const [q, ...nums]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: number[] = [];for (let k = 0; k < q; k++) { const a = nums[2 * k], b = nums[2 * k + 1]; let c = 0; for (let x = a; x <= b; x++) if (good[x]) c++; out.push(c);}console.log(out.join("\n"));import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static final int LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다 static int rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r; } public static void main(String[] args) throws Exception { 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; } boolean[] good = new boolean[LIMIT + 1]; for (int x = 0; x <= LIMIT; x++) good[x] = !composite[x] && !composite[rev(x)]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { StringTokenizer st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()); int c = 0; for (int x = a; x <= b; x++) if (good[x]) c++; out.append(c).append('\n'); } System.out.print(out); }}using System;using System.Text; class Program{ const int Limit = 9999; // 뒤집은 수도 9,999를 넘지 않는다 static int Rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r; } static void Main() { var isPrime = new bool[Limit + 1]; Array.Fill(isPrime, 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; } var good = new bool[Limit + 1]; for (int x = 0; x <= Limit; x++) good[x] = isPrime[x] && isPrime[Rev(x)]; int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(p[0]), b = int.Parse(p[1]); int c = 0; for (int x = a; x <= b; x++) if (good[x]) c++; sb.Append(c).Append('\n'); } Console.Write(sb); }}#include <iostream>#include <vector> const int LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다 int rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r;} int main() { std::ios::sync_with_stdio(false); 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<bool> good(LIMIT + 1); for (int x = 0; x <= LIMIT; x++) good[x] = isPrime[x] && isPrime[rev(x)]; int q, a, b; std::cin >> q; while (q--) { std::cin >> a >> b; int c = 0; for (int x = a; x <= b; x++) if (good[x]) c++; std::cout << c << "\n"; }}#include <stdbool.h>#include <stdio.h> #define LIMIT 9999 /* 뒤집은 수도 9,999를 넘지 않는다 */ static bool is_prime[LIMIT + 1];static bool good[LIMIT + 1]; static int rev(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r;} int main(void) { for (int k = 2; k <= LIMIT; k++) is_prime[k] = true; /* 0과 1은 false 그대로 */ for (int i = 2; i * i <= LIMIT; i++) { if (!is_prime[i]) continue; for (int j = i * i; j <= LIMIT; j += i) is_prime[j] = false; } for (int x = 0; x <= LIMIT; x++) good[x] = is_prime[x] && is_prime[rev(x)]; int q, a, b; scanf("%d", &q); while (q--) { scanf("%d %d", &a, &b); int c = 0; for (int x = a; x <= b; x++) if (good[x]) c++; printf("%d\n", c); } return 0;}LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다 // 에라토스테네스의 체: 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] = 거짓; } }} 뒤집기수(x){ r = 0; 동안 (x > 0) { r = r * 10 + x % 10; x = 수학.몫(x, 10); } 돌려주기 r;} good = 새목록(LIMIT + 1, 거짓);반복 (x = 2; x <= LIMIT; x++){ 만약 (isPrime[x] && isPrime[뒤집기수(x)]) { good[x] = 참; }} q = 콘솔.줄읽기().수로변환();반복 (k = 0; k < q; k++){ p = 콘솔.수들읽기(); c = 0; 반복 (x = p[0]; x <= p[1]; x++) { 만약 (good[x]) { c++; } } 콘솔.쓰기(c);}