[BOJ-1747][에라토스테네스의 체/문자열 처리] 소수&팰린드롬 - Java

문제 바로가기

1747번: 소수&팰린드롬

 

소수이면서 팰린드롬인 수를 구하는 문제입니다.

에라토스테네스의 체를 이용해서 소수를 구할 수 있습니다.

import java.io.*;

public class Main {
	static final int MAX = 1003001;

	public static boolean check(int num) {
		StringBuilder str = new StringBuilder();
		str.append(num);
		if(str.toString().equals(str.reverse().toString()))return true;
		else return false;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		boolean[] isNotPrime = new boolean[MAX + 1];
		int N = Integer.parseInt(br.readLine());
		isNotPrime[0] = true;
		isNotPrime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(MAX); i++) {
			for(int j = i*i; j <= MAX; j += i) {
				isNotPrime[j] = true;
			}
		}
		
		for(int i = N; i <= MAX; i++) {
			if(!isNotPrime[i] && check(i)) {
				System.out.println(i);
				break;
			}
		}
        
	}
}

 

우선 입력으로 들어올 수 있는 최대 값인 1000000의 답을 생각해보고 MAX 값을 잡았습니다.

 

그리고 에라토스테네스의 체를 사용해서 소수를 만들어 줍시다.

2~MAX 까지의 수를 체크할 때, i가 소수가 아니면 i의 배수도 소수가 아니니깐 넘어가주고,

i의 제곱부터 소수인지 체크를 해주기 때문에 최대 루트 MAX 까지만 봐주면 된답니다!

 

MAX까지의 수들이 각각 소수인지 아닌지 판별해주고, N부터 MAX 까지 돌려주면서 팰린드롬인지 체크해줍니다.

StringBuilder로 만들어서 reverse 해서 같은지 확인하면 끝입니다.

 

 

감사합니다!!