[백준]1747: 소수&팰린드롬 - JAVA

[백준]1747: 소수&팰린드롬

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

풀이

소수와 팰린드롬을 모두 판별하는 문제이다. 

 

소수를 판별할 때에는 에라토스테네스의 체 알고리즘을 사용하여 빠르게 소수를 판별해 주었다.

간단히 설명하자면 소수를 판별하기 위해 나누어 지는 수가 있는지 확인할 때 나누어지는 수의 범위를 제곱근으로 줄여 빠르게 판별할 수 있다. 

 

팰린드롬은 간단하게 입력받은 숫자를 문자열로 변경해 첫 문자와 마지막 문자에서 시작해 한 자리씩 이동하며 문자가 달리지는 순간 팰린드롬이 아니게 되므로 false를 반환하도록 하였다. 

 

어렵지 않은 문자열 문제였당!

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        for(int i = n; ; i++) {
            if(isPalindrome(i) && isPrime(i)) {
                System.out.println(i);
                break;
            }
        }    
    }
    
    public static boolean isPalindrome(int n) {
        String num = Integer.toString(n);
        for(int i = 0; i <= num.length() / 2; i++) {
            if(num.charAt(i) != num.charAt(num.length() - i - 1)) return false;
        }
        return true;
    }
    
    public static boolean isPrime(int n) {
        if(n == 1) return false;
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) return false;
        }
        return true;
    }
}