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

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

1747번: 소수&팰린드롬

 

---

 

문제 설명

입력받은 수보다 큰 소수들 중에서 그 숫자와 그 숫자를 뒤집은 숫자와 같은 수를 출력하는 문제이다

ex) 101은 뒤집어도 101이므로 팰린드롬 수이다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static boolean prime[] = new boolean[1004002];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		prime();

		for (int i = n; i < 1004000; i++) {
			if (!prime[i]) {
				String str = String.valueOf(i);
				StringBuffer sb = new StringBuffer(str);
				String reverseStr = sb.reverse().toString();

				if (str.equals(reverseStr)) {
					System.out.println(i);
					break;
				}
			}
		}
	}

	static void prime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i]) {
				continue;
			}

			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}
}

코드설명

소수 구하는것은 에라토스테네스의 체를 이용하여 풀었다.

그리고 for문을 n부터 1004000까지 돌려 소수인지 아닌지 조건문을 넣었다.

(1004000까지 돌리는 이유는 n이상의 팰린드롬 수를 구하는 문제인데, n이 1000000까지 되기 때문에 출력이 백만이 넘을 수 있어 400정도를 더 넣었다.)

그리고 String으로 소수 숫자들을 가져오고, StringBuffer을 이용해서 뒤집은 수도 가져왔다.

그리고 만약 소수 숫자를 가진 str과 뒤집은 수를 가진 reverseStr의 값이 같다면 출력을 시켰다.