自然数 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()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
質問が多いので、エラトステネスの篩で 9,999 までの素数表を一度作っておき、質問ごとに表を読みます。
表は 0 番から 9,999 番までの 10,000 マスです。
大きさを 9,999 にすると最後のマスがなく、Python・Java・C#・Craykon は範囲外エラーで止まり、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)、Craykon 新リスト(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 と Craykon の / は小数まで割るので、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);}