[BOJ-1747][문자열] 소수&팰린드롬 -Java

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

1747번: 소수&팰린드롬

package BOJ_String;

import java.util.Scanner;

public class boj_1747_소수_팰린드롬 {
	public static void main(String[] args) {
		int MAX=1100000;
		boolean isPrime[]=new boolean[MAX+1];
		
		Scanner sc=  new Scanner(System.in);
		int N=sc.nextInt();
		N = N==1 ? 2:N;
		
		for(int i=2; i<=MAX; i++) {
			for(int j=2; i*j<=MAX; j++) {
				isPrime[i*j]=true;
			}
		}
		
		for(int i=N; i<=MAX; i++) {
			if(isPrime[i]) continue;
			else { //소수 일때 
				if(isPalindrome(i)) {
					System.out.println(i);
					break;
				}
			}
		}
	}

	private static boolean isPalindrome(int i) {
		String str=Integer.toString(i);
		int left=0;
		int right=str.length()-1;
		while(left<=right) {
			if(str.charAt(left++)!=str.charAt(right--)) return false;
		}
		return true;
	}

}

소요시간 : 15분

 

 

우선 에라토스테네스의 체를 통해서 소수들을 구해줍니다!!

그런데 문제에서 N이 1,000,000까지이기 때문에 1,000,000까지만 소수를 구하는 게 아니라

그다음 큰 수 까지 구해줘야 합니다. 저는 1,1000,000 정도 돌리면 하나 이상은 나오겠지 라고 생각해서 MAX값을 저렇게 잡았습니다!

 

에라 토스 네테스의 체를 이용해 소수를 구했다면 팰린드롬인지만 확인해주면 끝입니다!

팰린드롬 구할 때는 인덱스를 처음, 끝 이렇게 두 개를 두고 좁혀가면서 확인했습니다.

 

 

에라토스테네스의 체가 뭔지 모르시겠다면 이 글에 잘 설명되어 있습니다 ㅎㅎ

dkwjdi.tistory.com/133?category=924260

에라토스테네스의 체 - 소수구하기

끝~