[백준] 2023 신기한 소수 - 구현

문제 링크 : https://www.acmicpc.net/problem/2023

🍊해결방법

• 메모리가 4MB로 에라토스테네스의 체 사용 불가
• 자리수에 있는 수를 하나씩 모두 보면서 각각의 수를 신기한 소수인지 판별하기엔 시간초과
• 모든 수를 과연 다 볼 필요가 있을까?
• 예를들어 2400에서 24를 보는 순간 소수가 아니므로 2400번대는 볼 필요가 없다 2500대로 넘어가자
• 이런 식으로 구현해서 해결

😀풀이

import java.util.*;
import java.io.*;

public class Main {



    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        if(N == 1){
            System.out.println(2);
            System.out.println(3);
            System.out.println(5);
            System.out.println(7);
            return;
        }

        int num = 1;
        for(int i=1; i<N; i++){
            num *= 10;
        }

        StringBuilder sb = new StringBuilder();

        int i = num;

        while(i < num*10){

            boolean isPalindrome =  true;

            int plus = 1;

            // 맨 왼쪽부터 1자리 부터 N자리까지의 수가 소수인지 확인
            for(int j=num; j>=1; j/=10){

                int tmp = i/j;

                if (tmp == 1 || tmp == 0){
                    plus = tmp*j + j;

                    isPalindrome = false;
                    break;
                }

                boolean flag = true;
                for(int k=2; k*k<=tmp; k++){

                    if(tmp%k == 0){
                        flag = false;
                        break;
                    }
                }

                // 이미 해당 자리수의 수가 소수가 아니다
                if(!flag){

                    plus = tmp*j + j;

                    isPalindrome = false;
                    break;
                }

            }

            if (isPalindrome){
                sb.append(i+"\n");
                i++;
            }
            else
                i = plus;
        }


        System.out.println(sb);


    }// end main




}