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

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

 

 

 

출처

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

 

 

문제

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

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

 

 

 

입력

첫째 줄에 N이 주어진다.

 

 

 

출력

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

 

 

 

 

입출력 예

 

 

 

걸린 시간

약 44분 걸렸다.

 

 

 

접근 방법

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

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

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

 

 

 

내 코드

 

 

 

고려할 점

1. 에라토스테네스의 체

2. 팰린드롬 판별