b진법으로 적은 수 하나가 장부에 번져서, 몇몇 자리를 읽을 수 없게 되었다.
읽을 수 없는 자리는 ?로, 나머지 자리는 0–9와 A–Z(A = 10, …, Z = 35)로 주어진다.
?마다 0부터 b − 1까지의 숫자 하나를 넣어 수를 완성한다.
수가 두 자리 이상이면 맨 앞 자리는 0이 될 수 없다(한 자리 수 0은 된다).
완성한 수 가운데 소수가 몇 개인지 출력하라.
하나 이상이면 가장 작은 소수와 가장 큰 소수를 한 줄씩 더 출력한다.
각 줄에는 그 수의 b진법 표기(대문자, 주어진 자리 수 그대로)와 10진법 값을 빈칸 하나로 띄워 쓴다.
소수는 1과 자기 자신으로만 나누어떨어지는 1보다 큰 수다.
입력
첫 줄에 b, 둘째 줄에 패턴(빈칸 없음). 2 ≤ b ≤ 36, 패턴의 길이 ≥ 1, ?가 아닌 자리는 b보다 작은 숫자, 길이가 2 이상이면 맨 앞은 0이 아니다. ?가 k개일 때 bᵏ ≤ 2,000이고, ?를 모두 b − 1로 채운 값도 100,000,000보다 작다.
출력
소수의 개수. 1 이상이면 이어서 "가장 작은 소수의 b진법 표기 10진법 값", "가장 큰 소수의 b진법 표기 10진법 값" 두 줄
예시 1 · stdin
16
?D
stdout
5
1D 29
AD 173
예시 2 · stdin
2
?
stdout
0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
완성한 수는 1억 미만이라 1억 칸짜리 체를 만들고 싶어지지만, 그러면 메모리가 크고 크레이콘 목록은 10,000칸까지예요. 합성수 n은 √n 이하의 소인수를 꼭 가지니, 1만 미만 소수만 체로 구해 두고 그 소수로 나눠 보면 돼요(p * p > n에서 멈춤). 이 멈춤을 빼면 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), 크레이콘 DIGITS.자리찾기(ch)·DIGITS[v]. 몫은 Python //, JavaScript·TypeScript Math.floor(c / b), 크레이콘 수학.몫(c, b)(/는 소수점 아래까지 나눠요). 함정은 ① 1을 소수로 세기, ② 맨 앞이 0인 채우기도 세기(예시 1의 0D = 13은 소수지만 세지 않아요), ③ 1만 칸 체로 1억 미만 값을 바로 찾기(칸 밖이에요)예요.
Pythonmain.py · 47 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
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);}