백준 2023 신기한 소수 python, java

소수라는 걸 보자마자 에라토스테네스의 체에서 출발했는데 제약조건이 있어서 다르게 생각해야했다.

📜 문제 바로 가기 : 신기한 소수

제출 코드

파이썬

import sys
input = sys.stdin.readline

N = int(input())

def isPrimeNumber(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def solve(num):
    if len(str(num)) == N:
        if isPrimeNumber(num) == True:
            print(num)
        return
    
    for i in range(10):
        k = num*10 + i
        if isPrimeNumber(k) == True:
            solve(k)

for i in [2, 3, 5, 7]:
    solve(i)

자바

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

public class Main {
    static final Main mySolve = new Main();
    static int N;
    static ArrayList<Integer> answer;
    static int[] one_prime = new int[]{2, 3, 5, 7};

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

        N = Integer.parseInt(br.readLine());
        answer = new ArrayList<>();

        for (int num : one_prime) {
            mySolve.solve(num);
        }

        for (Integer ans : answer) {
            System.out.println(ans);
        }
    }

    public boolean isPrimeNumber(int n) {
        double sqrt_num = Math.sqrt(n);
        for (int i = 2; i < Math.floor(sqrt_num)+1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;

    }

    public void solve(int num) {
        if (Integer.toString(num).length() == N) {
            if (isPrimeNumber(num) == true) {
                answer.add(num);
            }
            return ;
        }

        for (int i = 0; i < 10; i++) {
            int k = num*10 + i;
            if (isPrimeNumber(k) == true) {
                solve(k);
            }
        }
    }
}

---

접근방법

자리수(N)이 8까지 주어진다. 에라토스체네스의 체로 구한다면 99999999이하의 모든 소수를 찾아야 되는데 일단 이 숫자만 576만개 정도가 나온다. 또한 에라토스체네스의 체 알고리즘 수행에서 2로 나눠지는 숫자들만 카운트 해본다해도 거의 1억번의 연산이 필요하다.

그래서 생각한게 모든 소수를 다 구하지 말고 특정수가 소수인지만 판단해보기로 했다.
하지만 N = 8이라면 10000000 ~ 99999999 까지 숫자들에 대해 생각해봐야되는데 역시 로컬환경에서 돌려만 봐도 느리다.

해답은 문제설명에 있었다.

왼쪽 1자리가 소수여야한다. 그리고 우리는 1자리 숫자 중 소수인 수를 알고 있다.
2, 3, 5, 7...
즉 앞자리가 2, 3, 5, 7인 숫자만 고려해주면 되기에 시간을 줄일 수 있다.

수정

아니다! 고려해야되는 앞자리가 4개라서 시간을 줄일 수 있었던것이 아니었다.
생각해보니 앞자리 4개만 고려하든 9개를 고려하던 결과적으로는 시간의 차이가 없다고 봐도 될거 같다. 왜냐하면 임이의 10보다 작은 자연수가 소수인지 아닌지를 판단하는 것은 매우 빠르게 연산이 가능하기 때문이다.
시간을 줄일 수 있었던 이유는 자릿수를 하나하나 늘려가며 백트래킹을 적용했기 때문이었다.
32739223를 볼때 3, 32, .. 점점 늘려가면서 중간에 소수가 아닌 수가 나오면 그 수를 버리고 다음 수를 보는 백트래킹을 적용했기 때문이었다.