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

문제

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

1747번: 소수&팰린드롬

숫자 N이 주어졌을때, N보다 크거나 같은수중 소수이면서 팰린드롬인 수중 가장 작은 수를 찾는문제다.

 

풀이

에라토스테네스의 채를 이용해 풀은문제다.

 

우선, 에라토스테네스의 채의 최대 범위를 지정해주기위해, N = 1,000,000일때, 소수이면서 팰린드롬인 수중 가장 작은수를 찾아보면, 1003001 이라는것을 알수있다.

 

따라서, 소수를 걸러주기위한 check배열의 값은 1003001보다 크면된다.

 

탐색을 할때 N보다 큰 소수라면 해당 수가 팰린드롬인지 확인한다. 맞다면 출력하고 종료하고 아니라면 다음 정답 후보를 찾는다.

 

이때, 팰린드롬인지 확인을 쉽게하기위해, 팰린드롬 확인시 int를 string으로 형변환 시켜줬다.

(다른 문제를 풀때도 종종 사용하는 함수니까 처음본다면 잘 알아두도록 하자)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1747%20%EC%86%8C%EC%88%98%26%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC/main.cpp

devxb/JJUNalgo