[2023] 신기한 소수 in Java

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

2023번: 신기한 소수

---

 

1. 메모리 초과가 발생한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    static int n;
    static int afterNum;
    static int[] selectArray;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    public static void makeInt(int cnt) throws IOException { // cnt자리의 수를 뽑는다.
        if(cnt==n) {
            int temp = checkInt();
            if (temp!=0) {
                bw.write(temp+"\n");
            }
            return;
        }
        for(int i=1; i<=9; i++) {
            selectArray[cnt]=i;
            makeInt(cnt+1);
            selectArray[cnt]=0;
        }
    }
    
    public static int checkInt() {
        String answer="";
        for (int i : selectArray) {
            answer+=String.valueOf(i);
            afterNum = Integer.parseInt(answer);
            // 2. 소수 판별하기
            if (afterNum==1) return 0;
            for (int j = 2; j < afterNum; j++) {
                if(afterNum%j==0) {
                    return 0;
                }
            }
        }
        return afterNum;
    }
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        selectArray=new int[n];
        // 1. 숫자 만들기 (배열)
        makeInt(0);
        bw.close();
    }
 
}

---

2. 제곱근 범위 나누기법을 이용하여 해당 문제를 해결한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    static int n;
    static int afterNum;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    public static void makeInt(String s, int cnt) throws IOException { // cnt자리의 수를 뽑는다.
        if(cnt==n) {
            bw.write(s+"\n");
            return;
        }
        for(int i=1; i<=9; i++) {
            if(checkInt(Integer.parseInt(s+i))) {                
                makeInt(s+i, cnt+1);
            }
        }
    }
    
    public static boolean checkInt(int num) {
        if(num==1) return false;
        int sqrt= (int)Math.sqrt(num);
        
        for (int j = 2; j <= sqrt; j++) {
            if(num%j==0) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        // 1. 숫자 만들기 (배열)
        makeInt("",0);
        bw.close();
    }
 
}