[BOJ]伯俊2023号:不思議な少数Java(JAVA)1

1.質問

白駿2023号ポケモン小数-https://www.acmicpc.net/problem/2023
アルゴリズム分類-遡及,整数論
🥇 難易度-金メダル5

2.解答

この問題の核心は、1つ以上の数字を追加する過程で、多くの数字が簡単に通過できることです.
まず、何桁でも不思議な小数になるには、左から1桁は小数でなければなりません.
つまり、不思議な小数の第一位数は小数の2、3、5、7の一つであり、この場合に限って、以下の桁数を加えればよい.
1番目の数字2に0から9の次の数字を加算すると、20、21、22、24、25、26、27、28は小数ではなく、小数の23と29だけが次の数字を加算します.
残りの3、5、7についても同様に適用されます.
このようにしてNビットにビット数を追加し、ある数字がNビットに達すると、最終的にNビット数が小数であると判断し、小数であれば不思議な小数でしかないので、この値を出力することができる.

3.コード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        getResult(0,n);
        System.out.println(sb);
    }

    public static void getResult(int output, int n) {
        if (n == 0) {
            if (isPrime(output)) sb.append(output).append("\n");
            return;
        }
        for (int i=0; i<10; i++) {
            int next = output*10+i;
            if (isPrime(next)) getResult(next, n-1);
        }
    }

    public static boolean isPrime(int num) {
        if (num < 2) return false;

        for (int i=2; i<=Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

}

4.結果

5.解法

まず、少数の問題なので、最初に思いついたのはエラトネスのふるいで、この問題はメモリ制限なので4 MBしかありません.
エラトネスのふるいが使えない場合は、どの数が小数であるかを決定するのに要する時間がlognであり、N個の数を小数で判別するとNlognである.
Nは最大8ビットの数字であってもよいので、N log Nで放出するとタイムアウト2秒を超える.
他の方法を考えると,Nがいくらであっても,不思議小数の第一位数は小数でなければならないことが分かったが,再帰的に不思議小数になる可能性がある場合にのみ,桁数を増やす方法を考えた.