[백준 1747] 소수&팰린드롬 (자바)

백준 1747번 소수&팰린드롬 (자바)

 

 

 

출처

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

 

 

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 N이 주어진다.

 

 

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

 

 

 

입출력 예

 

 

 

걸린 시간

약 44분 걸렸다.

 

 

 

접근 방법

소수 구하는 방법과 팰린드롬 구하는 방법을 합치면 된다.

먼저 소수는 에라토스테네스의 체를 사용하여 1차원 배열을 하나 만들어서 소수인 경우만 true처리해주었다.

소수인 경우에 해당 숫자가 팰린드롬인지 확인하여 만약 팰린드롬이면 소수&팰린드롬을 만족하므로 바로 출력해주었다.

 

 

 

내 코드

	package guhyun;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class PrimePelin {
	/**
	* 백준 1747 소수&팰린드롬 (https://www.acmicpc.net/problem/1747)
	*/
	private static int n;
	private static boolean[] distinct = new boolean[1004001];
	public static void main(String[] args) throws IOException {
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	//소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램
	n = Integer.parseInt(reader.readLine());
	checkPrime();//소수판별
	int result = 0;
	for (int i=n; i<=1004000; i++) {
	//1. n보다 크거나 같고
	if (i < 10 && distinct[i]) {
	result = i;
	break;
	} else {
	if (checkPelin(Integer.toString(i)) && distinct[i]) {
	//3. 팰린드롬 확인
	result = i;
	break;
	}
	}
	}
	System.out.println(result);
	}
	private static boolean checkPelin(String num) {
	int start = 0;
	int end = num.length()-1;
	while (start <= end) {
	if (num.charAt(start) != num.charAt(end)) {
	return false;
	}
	start++;
	end--;
	}//while
	return true;
	}//checkPelin
	private static void checkPrime() {
	//2. 소수 판별 <- 에라토스테네스의 체
	for (int i=2; i<=1004000; i++) {
	distinct[i] = true;
	}
	int num = (int)Math.sqrt(1004000);
	for (int i=2; i<=num; i++) {
	if (distinct[i]) {
	for (int j=i; i*j<=1004000; j++) {
	distinct[i*j] = false;
	}
	}
	}
	}//checkPrime
	}

view raw PrimePelin.java hosted with ❤ by GitHub

 

 

 

고려할 점

1. 에라토스테네스의 체

2. 팰린드롬 판별