백준 1747 - 소수&팰린드롬

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

1. 유형

브루트 포스

 

2. 문제 접근

 

2-1. 설계

• 에라토스테네스의 체로 소수 판단
• 투 포인터를 사용하여 팰린드롬 확인

2-2. 주의할 점

 

입력값이 N이고 조건을 만족하는 정답은 N보다 더 커질 수 있습니다.

따라서 에라토스테네스의 체를 구할 때, 전체 크기를 100000보다 큰 소수를 구해서 정해줘야 합니다.

 

3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		boolean prime[] = new boolean[1004001];
		int len = 1004000;
		int N = stoi(st.nextToken());
		prime[1] = true;
		// 소수판단
		for (int i = 2; i < len; i++) {
			for (int j = i + i; j <= len; j += i) {
				prime[j] = true;
			}
		}
		List<Integer> ans = new ArrayList<>();
		for (int i = 2; i <= len; i++) {
			if (!prime[i]) {
				String s = String.valueOf(i);
				boolean exit = false;
				int m = s.length() / 2;
				int L, R;
				if (s.length() % 2 == 0) {
					L = m - 1;
					R = m;
				} else {
					L = m;
					R = m;
				}
				while (L >= 0) {
					if (s.charAt(L) != s.charAt(R)) {
						exit = true;
						break;
					}
					L -= 1;
					R += 1;
				}
				if(!exit)
					ans.add(i);
			}
		}
		for (int i = 0; i < ans.size(); i++) {
			if(ans.get(i) >= N) {
				System.out.println(ans.get(i));
				break;
			}
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}