백준 1747번(소수&팰린드롬)[JAVA]

풀이

에라토스테네스의 체를 이용하여 푼다.

1. 범위가 1~n까지인 배열 생성
2. 1은 소수가 아니므로 0으로 대체
3. 2를 제외한 2의 배수 모두 0으로 대체
4. 지워지지 않은 다음 수가 3이므로, 3을 제외한 3의 배수 모두 0으로 대체
5. 위 과정을 n의 제곱근까지 반복
6. 0이 아닌 값(소수)을 팰린드롬이 맞는지 판별

팁
수를 문자 배열로 치환한 후, 그 배열의 시작과 끝의 인덱스를 지정하여 두 인덱스 안의 있는 값들을 비교한다. 그 값이 같지 않다면 false를 반환하고, 같다면 시작 인덱스는 1 증가, 끝 인덱스는 1 감소를 하면서 배열의 중앙 인덱스에 도달할 때까지 반복 비교한다.

소스 코드

import java.util.*;

public class 소수와팰린드롬 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[10000001];
		
		for (int i = 2; i < arr.length; i++) {
			arr[i] = i;
		}
		
		for (int i = 2; i < Math.sqrt(arr.length); i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j = i+i; j < arr.length; j=i+j) {
				arr[j] = 0;
			}
		}
		int idx = n;
		while (true) {
			if (arr[idx] != 0) {
				if(isPalindrome(arr[idx])) {
					System.out.println(arr[idx]);
					break;
				}
			}
			idx++;
		}
	}
	
	static boolean isPalindrome(int x) {
		char[] numSTR = String.valueOf(x).toCharArray();
		int low = 0;
		int high = numSTR.length-1;
		
		while (true) {
			if (low > high)
				break;
			
			if (numSTR[low] != numSTR[high]) {
				return false;
			}
			low++;
			high--;
		}
		
		return true;
	}
}

태클 감사합니다.
조언 환영입니다.