[알고리즘] 2023. 신기한 소수

0. 문제

 

2023번: 신기한 소수

 

---

1. 시간초과

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

//시간 초과
public class BOJ2023 {

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

        int start = (int)Math.pow(10, N-1) * 2; // 1은 소수가 아니다. 최상위 수가 1일 수 없다.
        int end = (int)Math.pow(10, N);
        next : for(int i = start; i<end; i++) { // N 자리 수
            //System.out.println("i : " + i);
            for(int j=N-1; j>=0; j--) { // 왼쪽부터 1자리 -> 2자리 -> ... -> N자리
                int num = i / (int)Math.pow(10, j); 

                //가지치기
                if(num > 9 && (num&1)==0) continue next; // 2자리 수부터 짝수면 안됨.

                //소수인지 확인
                int limit = (int)Math.sqrt(num); // 루트 num까지만 확인해도됨.
                //System.out.println("num : " + num);
                for(int k=2; k<=limit; k++) {
                    if(num % k == 0) continue next; // 소수가 아니면 통과
                }
            }
            sb.append(i).append("\n");
        }
        System.out.println(sb);
        br.close();
    }

}

 

---

2. 시간 줄이기

 

1. 왼쪽부터 1번째 자리에 들어올 수 있는 수 → 2, 3, 5, 7
2. 2 번째 ~ N 번째 자리에 들어올 수 있는 수 → 홀수
3. 어떤 수 num이 소수인지 확인하는 방법 → 2부터 num의 제곱근까지 나누어 떨어지면 안 된다.

 

위를 바탕으로 코드를 최적화한다.

 

먼저 수(i)를 만들고 특정 자리까지만 숫자(num)를 가져오기 위해서 Math.pow()를 사용했다.

 

무조건 숫자(i)를 만들고 각 자리의 수가 2, 3번 조건을 만족하는지 확인하다 보니 불필요한 연산이 발생했다.

 

1번과 2번 조건을 만족하는 숫자만 생성하고 3번 조건을 만족하는지 확인하면 불필요한 연산을 줄일 수 있다.

 

import java.util.Scanner;

public class Main {

    static int N;
    static StringBuffer sb;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        sb = new StringBuffer();

        // 1. 왼쪽부터 1번째 자리에 들어올 수 있는 수 → 2, 3, 5, 7
        int[] arr = {2, 3, 5, 7};
        for(int first : arr){
            solve(1, first);
        }

        System.out.println(sb);
        sc.close();
    }

    public static void solve(int depth, int num){
        if(depth==N){
            sb.append(num).append("\n");
            return;
        }
        // 2. 2 번째 ~ N 번째 자리에 들어올 수 있는 수 → 홀수
        int next = num * 10;
        for(int i=1; i<10; i+=2){
            if(!check(next+i)) continue; //소수가 아니면 통과
            solve(depth+1, next+i);
        }
    }
    // 3. 어떤 수 `num`이 소수인지 확인하는 방법 → 2부터 `num`의 제곱근까지 나누어 떨어지면 안된다.
    public static boolean check(int num){
        int limit = (int)Math.sqrt(num);
        for(int i=2; i<=limit; i++){
            if(num%i==0) return false; // 아니면 false;
        }
        return true;// 소수면 true
    }
}

재귀함수로 구현하면서 num에 이전 결괏값을 저장하다 보니 계산량도 줄었다.

 

---