エラトステネスの篩進数変換全探索P0182

にじんだ帳簿の素数

帳簿に 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

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

完成した数は 1 億未満なので 1 億マスの篩を作りたくなりますが、メモリが大きく、Craykon のリストは 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)、Craykon DIGITS.位置検索(ch)・DIGITS[v]。
商は Python //、JavaScript・TypeScript Math.floor(c / b)、Craykon 数学.商(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] = 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])

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);}