[백준] 1747 소수&팰린드롬

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

2020-11-27

---

import java.util.Scanner;
 
public class Main1747 {
    public static int N;
    public static int length = 1003001;
    public static boolean vtd[];
    
    public static void prime() {
        vtd[0] = vtd[1] = true;
        for(int i = 2; i <= Math.sqrt(length); i++) {
            if(vtd[i]) continue;
            for(int j = i; (i*j) <= length; j++) {
                vtd[i*j] = true;
            }
        }
    }
    
    public static boolean check(int x) {
        StringBuilder sb = new StringBuilder(String.valueOf(x));
        if(sb.toString().equals(sb.reverse().toString())) return true;
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        vtd = new boolean[length+1];
        prime();
        N = sc.nextInt();
        int num = 0;
        for(int i = N; i <= length; i++) {
            if(!vtd[i]) { //소수이면서
                if(check(i)) {
                    num = i;
                    break;
                }
            }
        }
        System.out.println(num);
        
    }
}
 

 

1. 소수인 수를 일단 에라토스테네스의 체를 이용하여 모두 구했다.

 

2. N 부터 length까지 돌면서 소수인 경우 check함수를 통해서 팰린드롬인지 체크했다. length값은 N의 범위에서 1,000,000 기준으로 나올 수 있는 소수이면서 팰린드롬인 수인 1,003,001로 잡았다. 

 

3. 소수이면서 팰린드롬인 가장 작은 수를 찾으면 되므로, 찾는 즉시 함수를 종료했다.

 

 

+) 작년 3월에 풀었다가 틀렸던 흔적이 있어서 봤더니, 범위 값을 제대로 체크를 안 해줘서 N이 1,000,000 일 때 정답을 출력해주지 못해서 그런거였다.