[백준] 2023 신기한 소수 자바

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

메모리가 4MB로 작아서 에라토스테네스의 체는 사용이 불가능하다.

그리고 앞자리부터 더해가면서 소수인지 판별해가는 아이디어가 중요했다. 

import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void recursion(int n,int count){
        if(count == 0){
           sb.append(n+"\n");
           return;
        }else{
            for (int i = 1; i <= 9; i++) {
                int temp = n*10+i;
                if (isPrime(temp)) {
                   recursion(temp,count-1);
                }
            }
        }
    }
    
    public static boolean isPrime(int n){
        if(n==1) return false;
        for (int i=2; i<=Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        recursion(0,n);
        
        System.out.println(sb);
    }
}