[백준] 2023 신기한 소수 (java)

 

2023번: 신기한 소수

 

해설

메모장에 써보면서 실험해본 결과, 맨 앞자리엔 2, 3, 5, 7이 올 수 있고, 그 이후에는 1, 2, 3, 5, 7이 올 수 있다는 사실을 알 수 있었다. 숫자 크기상 에라스토테네스의 체를 쓰기에는 어려움이 있었고, 간단하게 제곱수까지만 반복문을 통해 소수임을 판별할 수 있게 만들었다.

 

check에는 문자열 s와 몇째자리 수까지 받았음을 나타내는 num을 파라미터로 받아서 소수임이 판별나면 check 메소드를 재귀로 돌렸고, num이 N과 같아지면 basis part, 지금까지 만들어낸 수를 출력하고 해당 메소드를 탈출한다.

 

그런식으로 만들 수 있는 모든 수를 만들어서 출력하는 것으로 답을 만들어낼 수 있었다.

풀이

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

// 백준 2023 신기한 소수
public class Question6my {

    static int answer=0;
    static int[] arr= {1,2,3,5,7,9};
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        check("2", 1);
        check("3", 1);
        check("5", 1);
        check("7", 1);

    }

    private static void check(String s, int num) {
        int n = Integer.parseInt(s);
        for(int i=2;i*i<=n;i++) {
            if(n%i==0) return;
        }
        if(num==N) {
            System.out.println(n);
            return;
        }
        for(int i=0;i<arr.length;i++) {
            check(s+arr[i], num+1);
        }

    }
}