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

원본 링크 : https://www.acmicpc.net/problem/2023

---

문제설명

 

 

소스코드

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

public class Boj_2023
{
    static int n;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }

    static void DFS(int num, int digit)
    {
        if(digit == n)
        {
            if(isPrime(num)) System.out.println(num);
            return;
        }
        for(int i = 1; i < 10; ++i)
        {
            if(i % 2 == 0) continue; // 짝수라면 더 이상 탐색할 필요 없음
            if(isPrime(num * 10 + i)) DFS(num * 10 + i, digit + 1); // 소수라면 자릿수를 늘리고, 재귀 호출
        }
    }

    static boolean isPrime(int num)
    {
        for(int i = 2; i <= num / 2; ++i)
        {
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

설명

1. 우선 자릿수가 한 개인 소수는 2, 3, 5, 7 이므로 이 수부터 탐색을 시작한다.(4, 6, 8, 9를 제외한 가지치기 방식)
2. 현재 수 * 10 + i를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀함수를 호출한다.(단 i가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 i가 짝수인 경우를 제외)
3. 이 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력

소수를 판별하는 방법은 보통 에라토스테네스의 체를 사용하지만 이 문제는 단순한 소수 판별 함수를 사용해도 시간 안에 풀 수 있다.