백준 2023. 신기한 소수

문제 : 백준 2023. 신기한 소수

문제

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

풀이

아! 문제 보고 어 이거 지난번에 했던 그런 류의 문제인가 싶었다. 맞기도 하다. 소수 판별을 위해 에라토스테네스의 체를 사용하여 소수 리스트를 생성하여 접근하려고 했다.
N이 최대 8이므로 100,000,000 이하의 배열을 생성하고 각 인덱스마다 소수인지를 판별하여 소수 리스트를 생성하고, n 자리수가 들어오면 해당 자리수 인덱스부터 탐색을 하려고 했다.
암 당연히 메모리 초과가 나버렸지 뭐얌 빠끄

우선 에라토스테네스의 체를 알고 있다는 점과 그 점으로 접근한다는 것까진 맞았다. 다만 배열을 생성하지 않고 2부터 모든 수를 나눠서 소수인지 아닌지를 판별하였다.

첫번째 자리도 소수여야하므로 시작할 수 있는 수는 [2, 3, 5, 7] 로 시작한다.
첫번째 자리수 x 10을 하고 한 자리를 더해줄 건데 이때 더해주는 수는 짝수가 되면 안된다.
짝수 더해주면 바로 끝이니 굳이 짝수를 안넣어주고 홀수들을 추가해주고 소수인지 판별한다.

풀이 코드 java

import java.io.*;

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

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

        int[] primeOne = new int[]{2, 3, 5, 7}; //소수인 첫번째 자리수

        if (n == 1) {
            for (int i : primeOne) {
                System.out.println(i);
            }
        }
        else
            for (int i : primeOne) {
                dfs(i, 0);
            }
    }

    static void dfs(int num, int k) {
        //System.out.println("dfs");
        if (isPrime(num)) {
            if (k == n-1) {
                //System.out.println("k = " + k);
                System.out.println(num);
            }
            else
                for (int i = 1; i < 10; i = i + 2) {
                    //System.out.println(num);
                    //System.out.println("k = " + k);
                    dfs(num * 10 + i, k + 1);

                }
        }
    }

    static boolean isPrime(int num) {
        //System.out.println("isPrime");
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

풀이 코드 python

import math

n = int(input())

primeOne = [2,3,5,7]
def isPrime(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            return False
    return True


def dfs(num, k):
    if isPrime(num):
        if k == n-1:
            print(num)
        else:
            for i in range(1,10,2):
                dfs(num*10+i, k+1)



if n == 1:
    for i in primeOne:
        print(i)
else:
    for i in primeOne:
        dfs(i, 0)