백준 1747 - 소수&팰린드롬

Java

1747 번 - 소수&팰린드롬

문제

접근 방법

일정 범위 내의 수에서 소수를 전부 구한 다음에 팰린드롬 수를 구하면 되는 문제이다.

소수를 구하는 방법은 에라토스테네스의 체를 사용하였다.

간단해 보이는 문제였지만, 함정으로 고민을 하였던 문제이다.
먼저, 주어진 수 N (1 ≤ N ≤ 1,000,000)보다 크거나 같은 소수&팰린드롬 수를 구하는 문제이다.
따라서 답으로 나올 수 있는 수는 1000000보다 더 큰 수가 나온다.

이에 1005000까지 범위의 수에 속하는 소수를 구하였다.

또한, 1은 소수가 아니므로 제외하였다.

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
		int MAXNUM = 1005000;	// 1부터 1005000까지 수를 구한다.
		
    	n = stoi(br.readLine());
    	boolean[] number = new boolean[MAXNUM + 1];
    	int root = (int)Math.sqrt(MAXNUM) + 1;
    	
    	// 에라토스테네스의 체
    	for(int i = 2; i <= root; i++) {
    		int idx = i;
    		idx += i;
    		while(idx <= MAXNUM) {
    			number[idx] = true;
    			idx += i;
    		}
    	}
    	number[1] = true;	// 1은 소수가 아니다.
    	
    	int result = -1;
    	for(int num = n; num <= MAXNUM; num++) {
    		if(number[num])
    			continue;
    		
    		if(findPelin(num)) {
    			result = num;
    			break;
    		}
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	
	// 펠린드롭인지 판별하는 메서드
	static boolean findPelin(int num) {
		String str = Integer.toString(num);
		int len = str.length();
		
		for(int i = 0; i < len / 2; i++) {
			if(str.charAt(i) != str.charAt(len - 1 - i))
				return false;
		}
		return true;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점