백준 1990 (소수인팰린드롬) - java

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

1990번: 소수인팰린드롬

문제 

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

 

유형 : 문자열(팰린드롬) + 소수 판정(에라토스테네스의 체)

 

접근 방식

• 해당 범위 ( n 이상 m 이하 )의 소수를 모두 찾는다. -> 소수 판정 알고리즘 사용
• 팰린드롬 알고리즘을 통해 판단

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;


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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        boolean[] isPrime = new boolean[m+1];

        StringBuilder sb = new StringBuilder();

        for(int i=2;i<=Math.sqrt(m);i++){
            if(!isPrime[i]){
                int j= 2;

                while(i * j <= m){
                    isPrime[i*j] = true;
                    j = j + 1;
                }
            }
        }

        for(int i=n;i<=m;i++){
            if(!isPrime[i] && palindrome(String.valueOf(i))){
                sb.append(i+"\n");
            }
        }

        sb.append("-1\n");
        System.out.print(sb);
        br.close();
    }

    static boolean palindrome(String cur){
        char[] arr = cur.toCharArray();
        int len = arr.length - 1;

        for(int i=0;i<arr.length/2;i++){
            if(arr[i] == arr[len - i]){
                continue;
            }

            return false;
        }

        return true;
    }

}