[Baekjoon] 1990_소수인팰린드롬

Gold V

문제(출처: https://www.acmicpc.net/problem/1990)

---

< 소수인팰린드롬 >

 

문제 풀이 

 

에라토스테네스의 체 알고리즘을 사용해서 b까지 소수를 구한다. a이상 b이하 값 중 소수인 값을 팰린드롬인지 확인하여 팰린드롬이라면 출력한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _1990_ { // 소수인팰린드롬

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		boolean arr[] = new boolean[b + 1];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i < (b + 1) / 2 + 1; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < b + 1; j += i) {
					arr[j] = true;
				}
			}
		}

		boolean flag = false;
		for (int i = a; i <= b; i++) {
			if (!arr[i]) {
				String str = Integer.toString(i);
				for (int j = 0; j < str.length() / 2; j++) {
					if (str.charAt(j) != str.charAt(str.length() - 1 - j)) {
						flag = true;
						break;
					}
				}
				if (!flag) {
					bw.write(i + "\n");
				}
				flag = false;
			}
		}
		bw.write("-1");
		bw.flush();
	}
}

변수)
a, b : 두 자연수
arr : 소수 판별
flag : 팰린드롬 여부

 

두 자연수 a, b를 입력받는다. 에라토스테네스의 체 알고리즘을 사용하여 b까지 소수를 구한다. a이상 b이하인 값 중에서 소수인 값을 먼저 찾는다. 소수라면 팰린드롬인지 확인하여 팰린드롬이라면 출력한다. 마지막 줄에는 -1을 출력한다.

---

* 처음 시간초과한 코드를 수정 없이 제출했더니 통과했다.

---