For a positive integer x, let rev(x) be the number read from its decimal digits backwards. Leading zeros are dropped (120 → 21, 7 → 7).
If both x and rev(x) are prime, x is called 'prime both ways'.
rev(x) may equal x. So 2, 11 and 101 are prime both ways too.
A prime is an integer greater than 1 divisible only by 1 and itself. 1 is not prime.
The first line gives the number of queries q, and each of the next q lines gives two integers a and b separated by a space.
For each query print, on its own line, how many numbers from a to b inclusive are prime both ways.
Input
1 ≤ q ≤ 100, 1 ≤ a ≤ b ≤ 9,999
Output
q lines, a count for each query
Example 1 · stdin
3
1 10
10 20
100 199
stdout
4
3
12
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
With many queries, build a prime table up to 9,999 once with the sieve of Eratosthenes and just read it for each query. The table has 10,000 slots, 0 to 9,999. If you make it size 9,999 the last slot is missing: Python, Java, C# and Craykon stop with an out-of-range error, and C silently reads past the array. Creating it: Python [True] * (LIMIT + 1), JS/TS new Array(LIMIT + 1).fill(true), C# new bool[LIMIT + 1] then Array.Fill, C++ std::vector<bool>(LIMIT + 1, true), Craykon NewList(LIMIT + 1, true). Java boolean[] and C static arrays start all false, so store 'is composite' instead or fill true from 2. Mark 0 and 1 as not prime first (forget 1 and you count it). The trap is the size of the sieve. If you sieve only up to the query's b, you cannot tell whether a reversed number larger than b, like 31 from 13, is prime. Reversed numbers never exceed 9,999 either, so always sieve to 9,999. The well-known 'emirp' requires the reversed number to differ from the original, but this problem counts 2, 11, 101 and the like. The range includes b, so loop while x <= b. When reversing digits, / in JS/TS and Craykon divides into decimals, so use Math.floor(x / 10) and Mathf.Quot(x, 10).
Pythonmain.py · 27 lines
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 += 1def rev(x): r = 0 while x > 0: r = r * 10 + x % 10 x //= 10 return rgood = [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]))
JavaScriptmain.js · 26 lines
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"));
TypeScriptmain.ts · 27 lines
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"));
JavaMain.java · 39 lines
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); }}
C#Main.cs · 44 lines
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); }}
C++main.cpp · 34 lines
#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"; }}
Cmain.c · 35 lines
#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;}
Craykonmain.cray · 51 lines
LIMIT = 9999; // 뒤집은 수도 9,999를 넘지 않는다// 에라토스테네스의 체: isPrime[k]는 k가 소수인지isPrime = NewList(LIMIT + 1, true);isPrime[0] = false;isPrime[1] = false;for (i = 2; i * i <= LIMIT; i++){ if (isPrime[i]) { for (j = i * i; j <= LIMIT; j += i) { isPrime[j] = false; } }}뒤집기수(x){ r = 0; while (x > 0) { r = r * 10 + x % 10; x = Mathf.Quot(x, 10); } return r;}good = NewList(LIMIT + 1, false);for (x = 2; x <= LIMIT; x++){ if (isPrime[x] && isPrime[뒤집기수(x)]) { good[x] = true; }}q = Console.ReadLine().ToNumber();for (k = 0; k < q; k++){ p = Console.ReadNumbers(); c = 0; for (x = p[0]; x <= p[1]; x++) { if (good[x]) { c++; } } Console.WriteLine(c);}