[백준 2023번] 신기한 소수 [JAVA]

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

 

 

 

1. 입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

 

 

2. 출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

 

 

3.문제풀이

처음에 시간을 위해 에라토스테네스의 체를 이용했는데 이를 사용하게 되면 메모리 초과가 나게 됩니다.

 

재귀를 돌릴때 10으로 나누면서 탐색을 진행하는데 값이 10보다 작아지는 경우 isPrime을 통해서 소수인지 판별하고 참/거짓을 return 하게 됩니다.

 

이때 리턴받은 값을 and를 통해 비교하게 되는데 참이 나온 경우에는 isPrime을 통해서 현재 값이 소수인지 판별하고 거짓이 나온 경우는 isPrime을 거치지 않게 되므로 시간적을 단축시킬 수 있습니다.

 

 

 

4.소스코드

import java.util.*;
import java.io.*;

public class Main {


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int N;

    static int number;
    static int number_l;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        number = (int) Math.pow(10, N-1);
        number_l = (int) Math.pow(10,N)-1;
        for(int i=number; i<=number_l; i++){
            if(check(i)){
                bw.write(i + "\n");
            }
        }
        bw.flush();
        bw.close();


    }
    static boolean check(int N){
        if(N < 10){
            return isPrime(N);
        }else{
            return check(N / 10) && isPrime(N);
        }
    }
    static boolean isPrime(int N){
        if(N < 2) return false;
        for(int i=2; i*i<= N; i++){
            if(N % i == 0){
                return false;
            }
        }
        return true;
    }
}