账本上一个用 b 进制写的数被弄脏了，有几位已经看不清。
看不清的位用 ?
表示，其余各位用 0–9 和 A–Z（A = 10，…，Z = 35）给出。
在每个 ?
中填入 0 到 b − 1 中的一个数字，把数补完整。
如果这个数有两位或更多，最高位不能是 0（一位数 0 可以）。
输出补完的数中有多少个是素数。
如果至少有一个，再各用一行输出最小的素数和最大的素数。
这两行写出该数的 b 进制表示（大写，位数与给出的相同）和十进制值，中间用一个空格隔开。
素数是只能被 1 和自身整除的大于 1 的数。
16 ?D
5 1D 29 AD 173
2 ?
0
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
补完的数小于 1 亿，很容易想开一个 1 亿格的筛，但那样内存很大，而且 Craykon 的列表最多 10,000 项。
合数 n 一定有不超过 √n 的素因数，所以只用筛求出 1 万以下的素数，再用这些素数去试除即可（在 p * p > n 时停止）。
去掉这个停止条件的话，当 n 本身就是筛里的素数时会被自己整除，被误判为合数。
有 k 个 ?
时共有 bᵏ 种填法；从 0 数到 bᵏ − 1，**把计数转成 b 进制，从低位起填进 ?
的位置**，就能按值从小到大走遍所有情况。
所以最先找到的素数最小，最后一个最大。
数字字符 → 值在 DIGITS 里查找，值 → 字符读取那个位置：Python DIGITS.index(c)/DIGITS[v]，JavaScript/TypeScript indexOf，Java DIGITS.indexOf(ch)/charAt，C# IndexOf，C strchr(DIGITS, ch) - DIGITS，C++ DIGITS.find(ch)，Craykon DIGITS.查找位置(ch)/DIGITS[v]。
商：Python //，JavaScript/TypeScript Math.floor(c / b)，Craykon 数学.商(c, b)（/ 会保留小数）。
陷阱是 ① 把 1 算作素数，② 把首位为 0 的填法也算进去（例 1 的 0D = 13 是素数但不算），③ 直接用 1 万格的筛去查 1 亿以下的值（越界）。
DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"LIMIT = 10_000 # 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 # 에라토스테네스의 체: 1만 미만 소수is_comp = [False] * LIMITprimes = []for i in range(2, LIMIT): if not is_comp[i]: primes.append(i) for j in range(i * i, LIMIT, i): is_comp[j] = True def is_prime(n): if n < 2: return False for p in primes: if p * p > n: break if n % p == 0: return False return True b = int(input())pattern = input().strip()holes = [i for i, c in enumerate(pattern) if c == "?"]k = len(holes)found = [] # (b진법 문자열, 값), 작은 값부터for code in range(b ** k): digits = list(pattern) # code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 for pos in reversed(holes): digits[pos] = DIGITS[code % b] code //= b if len(digits) > 1 and digits[0] == "0": continue # 맨 앞 0은 안 된다 value = 0 for c in digits: value = value * b + DIGITS.index(c) if is_prime(value): found.append(("".join(digits), value)) print(len(found))if found: print(*found[0]) print(*found[-1])const lines = require("fs").readFileSync(0, "utf8").split("\n");const DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";const LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 // 에라토스테네스의 체: 1만 미만 소수const isComp = new Array(LIMIT).fill(false);const primes = [];for (let i = 2; i < LIMIT; i++) { if (isComp[i]) continue; primes.push(i); for (let j = i * i; j < LIMIT; j += i) isComp[j] = true;} function isPrime(n) { if (n < 2) return false; for (const p of primes) { if (p * p > n) break; if (n % p === 0) return false; } return true;} const b = Number(lines[0]);const pattern = lines[1].trim();const holes = [];for (let i = 0; i < pattern.length; i++) if (pattern[i] === "?") holes.push(i);const total = b ** holes.length;let count = 0;let first = null;let last = null;for (let code = 0; code < total; code++) { const digits = pattern.split(""); // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 let c = code; for (let h = holes.length - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c = Math.floor(c / b); } if (digits.length > 1 && digits[0] === "0") continue; // 맨 앞 0은 안 된다 let value = 0; for (const ch of digits) value = value * b + DIGITS.indexOf(ch); if (isPrime(value)) { count++; const shown = `${digits.join("")} ${value}`; if (first === null) first = shown; last = shown; }}console.log(count === 0 ? "0" : `${count}\n${first}\n${last}`);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";const LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 // 에라토스테네스의 체: 1만 미만 소수const isComp: boolean[] = new Array<boolean>(LIMIT).fill(false);const primes: number[] = [];for (let i = 2; i < LIMIT; i++) { if (isComp[i]) continue; primes.push(i); for (let j = i * i; j < LIMIT; j += i) isComp[j] = true;} function isPrime(n: number): boolean { if (n < 2) return false; for (const p of primes) { if (p * p > n) break; if (n % p === 0) return false; } return true;} const b = Number(lines[0]);const pattern = lines[1].trim();const holes: number[] = [];for (let i = 0; i < pattern.length; i++) if (pattern[i] === "?") holes.push(i);const total = b ** holes.length;let count = 0;let first: string | null = null;let last: string | null = null;for (let code = 0; code < total; code++) { const digits: string[] = pattern.split(""); // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 let c = code; for (let h = holes.length - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c = Math.floor(c / b); } if (digits.length > 1 && digits[0] === "0") continue; // 맨 앞 0은 안 된다 let value = 0; for (const ch of digits) value = value * b + DIGITS.indexOf(ch); if (isPrime(value)) { count++; const shown = `${digits.join("")} ${value}`; if (first === null) first = shown; last = shown; }}console.log(count === 0 ? "0" : `${count}\n${first}\n${last}`);import java.io.*;import java.util.*; public class Main { static final String DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; static final int LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 static final List<Integer> primes = new ArrayList<>(); static boolean isPrime(int n) { if (n < 2) return false; for (int p : primes) { if (p * p > n) break; if (n % p == 0) return false; } return true; } public static void main(String[] args) throws IOException { // 에라토스테네스의 체: 1만 미만 소수 boolean[] isComp = new boolean[LIMIT]; for (int i = 2; i < LIMIT; i++) { if (isComp[i]) continue; primes.add(i); for (int j = i * i; j < LIMIT; j += i) isComp[j] = true; } BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int b = Integer.parseInt(in.readLine().trim()); String pattern = in.readLine().trim(); List<Integer> holes = new ArrayList<>(); for (int i = 0; i < pattern.length(); i++) if (pattern.charAt(i) == '?') holes.add(i); int total = 1; for (int i = 0; i < holes.size(); i++) total *= b; int count = 0; String first = null, last = null; for (int code = 0; code < total; code++) { char[] digits = pattern.toCharArray(); // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 int c = code; for (int h = holes.size() - 1; h >= 0; h--) { digits[holes.get(h)] = DIGITS.charAt(c % b); c /= b; } if (digits.length > 1 && digits[0] == '0') continue; // 맨 앞 0은 안 된다 int value = 0; for (char ch : digits) value = value * b + DIGITS.indexOf(ch); if (isPrime(value)) { count++; String shown = new String(digits) + " " + value; if (first == null) first = shown; last = shown; } } System.out.println(count == 0 ? "0" : count + "\n" + first + "\n" + last); }}using System;using System.Collections.Generic; class Program{ const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const int LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 static readonly List<int> primes = new List<int>(); static bool IsPrime(int n) { if (n < 2) return false; foreach (int p in primes) { if (p * p > n) break; if (n % p == 0) return false; } return true; } static void Main() { // 에라토스테네스의 체: 1만 미만 소수 var isComp = new bool[LIMIT]; for (int i = 2; i < LIMIT; i++) { if (isComp[i]) continue; primes.Add(i); for (int j = i * i; j < LIMIT; j += i) isComp[j] = true; } int b = int.Parse(Console.ReadLine().Trim()); string pattern = Console.ReadLine().Trim(); var holes = new List<int>(); for (int i = 0; i < pattern.Length; i++) if (pattern[i] == '?') holes.Add(i); int total = 1; foreach (int _ in holes) total *= b; int count = 0; string first = null, last = null; for (int code = 0; code < total; code++) { char[] digits = pattern.ToCharArray(); // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 int c = code; for (int h = holes.Count - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c /= b; } if (digits.Length > 1 && digits[0] == '0') continue; // 맨 앞 0은 안 된다 int value = 0; foreach (char ch in digits) value = value * b + DIGITS.IndexOf(ch); if (IsPrime(value)) { count++; string shown = new string(digits) + " " + value; if (first == null) first = shown; last = shown; } } Console.WriteLine(count == 0 ? "0" : count + "\n" + first + "\n" + last); }}#include <iostream>#include <string>#include <vector> const std::string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";const int LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다std::vector<int> primes; bool isPrime(int n) { if (n < 2) return false; for (int p : primes) { if (p * p > n) break; if (n % p == 0) return false; } return true;} int main() { // 에라토스테네스의 체: 1만 미만 소수 std::vector<bool> isComp(LIMIT, false); for (int i = 2; i < LIMIT; i++) { if (isComp[i]) continue; primes.push_back(i); for (int j = i * i; j < LIMIT; j += i) isComp[j] = true; } int b; std::string pattern; std::cin >> b >> pattern; std::vector<int> holes; for (int i = 0; i < (int)pattern.size(); i++) if (pattern[i] == '?') holes.push_back(i); int total = 1; for (size_t i = 0; i < holes.size(); i++) total *= b; int count = 0; std::string first, last; for (int code = 0; code < total; code++) { std::string digits = pattern; // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 int c = code; for (int h = (int)holes.size() - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c /= b; } if (digits.size() > 1 && digits[0] == '0') continue; // 맨 앞 0은 안 된다 int value = 0; for (char ch : digits) value = value * b + (int)DIGITS.find(ch); if (isPrime(value)) { count++; std::string shown = digits + " " + std::to_string(value); if (count == 1) first = shown; last = shown; } } std::cout << count << '\n'; if (count > 0) std::cout << first << '\n' << last << '\n';}#include <stdio.h>#include <string.h> #define LIMIT 10000 /* 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다 */ static const char DIGITS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";static int primes[LIMIT], nprimes = 0; int is_prime(int n) { if (n < 2) return 0; for (int i = 0; i < nprimes; i++) { int p = primes[i]; if (p * p > n) break; if (n % p == 0) return 0; } return 1;} int digit_value(char ch) { return (int)(strchr(DIGITS, ch) - DIGITS);} int main(void) { /* 에라토스테네스의 체: 1만 미만 소수 */ static char is_comp[LIMIT]; for (int i = 2; i < LIMIT; i++) { if (is_comp[i]) continue; primes[nprimes++] = i; for (int j = i * i; j < LIMIT; j += i) is_comp[j] = 1; } int b; char pattern[64], digits[64]; scanf("%d %63s", &b, pattern); int len = (int)strlen(pattern); int holes[64], k = 0; for (int i = 0; i < len; i++) if (pattern[i] == '?') holes[k++] = i; int total = 1; for (int i = 0; i < k; i++) total *= b; int count = 0, first_v = 0, last_v = 0; char first[64] = "", last[64] = ""; for (int code = 0; code < total; code++) { strcpy(digits, pattern); /* code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 */ int c = code; for (int h = k - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c /= b; } if (len > 1 && digits[0] == '0') continue; /* 맨 앞 0은 안 된다 */ int value = 0; for (int i = 0; i < len; i++) value = value * b + digit_value(digits[i]); if (is_prime(value)) { if (count == 0) { strcpy(first, digits); first_v = value; } strcpy(last, digits); last_v = value; count++; } } printf("%d\n", count); if (count > 0) printf("%s %d\n%s %d\n", first, first_v, last, last_v); return 0;}DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다(목록도 1만 칸까지) // 에라토스테네스의 체: 1만 미만 소수isComp = 新列表(LIMIT, 假);primes = [];循环 (i = 2; i < LIMIT; i++){ 如果 (!isComp[i]) { primes.添加(i); 循环 (j = i * i; j < LIMIT; j += i) { isComp[j] = 真; } }} 소수인가(n){ 如果 (n < 2) { 返回 假; } 遍历 (p 在 primes) { 如果 (p * p > n) { 跳出; } 如果 (n % p == 0) { 返回 假; } } 返回 真;} b = 控制台.读行().转数字();pattern = 控制台.读行().去空白();holes = [];循环 (i = 0; i < pattern.长度; i++){ 如果 (pattern[i] == "?") { holes.添加(i); }}total = 1;遍历 (h 在 holes){ total *= b;} count = 0;first = "";last = "";循环 (code = 0; code < total; code++){ // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 digits = []; 遍历 (ch 在 pattern) { digits.添加(ch); } c = code; 循环 (h = holes.数量 - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c = 数学.商(c, b); } 如果 (digits.数量 > 1 && digits[0] == "0") { 继续; // 맨 앞 0은 안 된다 } value = 0; text = ""; 遍历 (ch 在 digits) { value = value * b + DIGITS.查找位置(ch); text += ch; } 如果 (소수인가(value)) { count += 1; 如果 (count == 1) { first = text + " " + value; } last = text + " " + value; }}控制台.输出(count);如果 (count > 0){ 控制台.输出(first); 控制台.输出(last);}