A number written in base b in a ledger got smudged, and some of its digits can no longer be read.
Unreadable digits are given as ?, and the other digits as 0–9 and A–Z (A = 10, …, Z = 35).
Put one digit from 0 to b − 1 into each ? to complete the number.
If the number has two or more digits, its first digit cannot be 0 (the one-digit number 0 is allowed).
Print how many of the completed numbers are prime.
If there is at least one, also print the smallest prime and the largest prime, one per line.
Each of those lines has the number's base-b form (uppercase, with exactly the given number of digits) and its decimal value, separated by one space.
A prime is a number greater than 1 divisible only by 1 and itself.
Input
The first line has b, the second line the pattern (no spaces). 2 ≤ b ≤ 36, the pattern has length ≥ 1, every non-? digit is less than b, and if the length is 2 or more the first character is not 0. With k question marks, bᵏ ≤ 2,000, and filling every ? with b − 1 still gives a value below 100,000,000.
Output
The number of primes. If it is at least 1, two more lines: "base-b form of the smallest prime, its decimal value" and "base-b form of the largest prime, its decimal value"
Example 1 · stdin
16
?D
stdout
5
1D 29
AD 173
Example 2 · stdin
2
?
stdout
0
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
Completed numbers are below 100 million, so a 100-million-cell sieve is tempting, but it needs a lot of memory and Craykon lists hold at most 10,000 items. A composite n always has a prime factor ≤ √n, so sieve only the primes below 10,000 and try dividing by them (stop when p * p > n). Without that stop, a prime n inside the sieve divides itself and is wrongly called composite. With k question marks there are bᵏ fillings; counting from 0 to bᵏ − 1 and **writing the counter in base b into the ? slots, lowest digit into the rightmost ? first**, visits every filling in increasing value. So the first prime found is the smallest and the last is the largest. Digit character → value is a lookup in DIGITS, and value → character reads that position: 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.IndexOf(ch)/DIGITS[v]. The quotient is Python //, JavaScript/TypeScript Math.floor(c / b), Craykon Mathf.Quot(c, b) (/ keeps decimals). The traps are (1) counting 1 as prime, (2) counting fillings with a leading 0 (in example 1, 0D = 13 is prime but does not count), and (3) looking up values below 100 million directly in a 10,000-cell sieve (out of range).
Pythonmain.py · 47 lines
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] = Truedef is_prime(n): if n < 2: return False for p in primes: if p * p > n: break if n % p == 0: return False return Trueb = 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])
JavaScriptmain.js · 49 lines
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}`);
TypeScriptmain.ts · 50 lines
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}`);
JavaMain.java · 57 lines
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); }}
C#Main.cs · 64 lines
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); }}
C++main.cpp · 58 lines
#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';}
Cmain.c · 67 lines
#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;}
Craykonmain.cray · 98 lines
DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";LIMIT = 10000; // 값은 1억 미만이라 약수를 찾으려면 1만 미만 소수면 충분하다(목록도 1만 칸까지)// 에라토스테네스의 체: 1만 미만 소수isComp = NewList(LIMIT, false);primes = [];for (i = 2; i < LIMIT; i++){ if (!isComp[i]) { primes.Add(i); for (j = i * i; j < LIMIT; j += i) { isComp[j] = true; } }}소수인가(n){ if (n < 2) { return false; } foreach (p in primes) { if (p * p > n) { break; } if (n % p == 0) { return false; } } return true;}b = Console.ReadLine().ToNumber();pattern = Console.ReadLine().Trim();holes = [];for (i = 0; i < pattern.Length; i++){ if (pattern[i] == "?") { holes.Add(i); }}total = 1;foreach (h in holes){ total *= b;}count = 0;first = "";last = "";for (code = 0; code < total; code++){ // code를 b진법으로 써서 ?를 뒤(낮은 자리)부터 채운다 digits = []; foreach (ch in pattern) { digits.Add(ch); } c = code; for (h = holes.Count - 1; h >= 0; h--) { digits[holes[h]] = DIGITS[c % b]; c = Mathf.Quot(c, b); } if (digits.Count > 1 && digits[0] == "0") { continue; // 맨 앞 0은 안 된다 } value = 0; text = ""; foreach (ch in digits) { value = value * b + DIGITS.IndexOf(ch); text += ch; } if (소수인가(value)) { count += 1; if (count == 1) { first = text + " " + value; } last = text + " " + value; }}Console.WriteLine(count);if (count > 0){ Console.WriteLine(first); Console.WriteLine(last);}