백준 1747 소수&펠린드롬(Silver1)

정답코드

import java.util.*;

public class Main {

	static int N;
    //10000000보다 작은 가장 큰 소수는 10003002
	static int[] prime = new int[1003002];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		initialize_prime();
		
		
		for(int i = N; i<1003002; i++) {
			//숫자가 소수일 때만 재귀를 돌아준다 
			if(prime[i] != 0) {
				if( Pellindrome(Integer.toString(i))) {
					System.out.println(i);
					break;
				}
			}
		}	
		return; 
	}
	
	//에라토스테네스의 채 
	public static void initialize_prime() {
		for(int i = 2; i < 1003002; i++) {
			prime[i] = i;
		}
		
		for(int i = 2; i < 1003002; i++) {
			if(prime[i] == 0)continue;
			for(int j = 2*i; j < 1003002; j+=i) {
				prime[j] = 0;
			}
		}
	}
	
    //펠린드롬 판별 
	public static boolean Pellindrome(String num) {
		int temp = num.length()/2;
		for(int i = 0; i<temp; i++) {
			if(num.charAt(i)!=num.charAt(num.length()-1-i))return false;
		}
		return true;
	}

}

전략

• 가장 먼저 소수 판별부터 해야함 근데 숫자가 커서 일반적인 소수 판별법으론 불가

  • 에라토스테네스의 체 사용

• 소수일 경우엔 Pellindrome인지 확인