[Java] 백준 2023번 : 신기한 소수

1. 문제

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

2023번: 신기한 소수

 

 

2. 풀이과정

1. 재귀를 사용하여, n자리의 가능한 모든 순열을 구한다. 이때, 중간 값이 소수가 아닌 수는 가지치기로 return한다.

2. 해당 수가 sqrt(해당_수)보다 같거나 작은 값으로 나눠지는지 확인하여, 소수 여부를 판단한다.

 

*에라토스테네스의 체는 최대 크기가 boolean[100_000_000]인 배열이 사용된다. boolean은 하나에 1byte인데 여기서 메모리 제한이 4MB로 약 4_000_000byte까지 가능하므로 소수를 하나씩 판별하는 메서드를 구현했다.

import java.util.Scanner;

public class Main {
    static int n;

    public static boolean isPrime(int num){
        if(num < 2){
            return false;
        }
        for(int i=(int)Math.sqrt(num); i>=2; i--){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

    public static void findSpecialNum(int cnt, int num){
        if(cnt>=n){
            System.out.println(num);
            return;
        }
        for(int i=1; i<10; i++){
            int next = num*10+i;
            if(!isPrime(next)){continue;}
            findSpecialNum(cnt+1, next);
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        findSpecialNum(0, 0);
    }
}

 

결과