문제 1747. 소수&팰린드롬 (대학생 기본반 1번)

난이도 :  실버 1

 

문제 요약 설명

자연수 N이 주어졌을 때, N보다 크거나 같은 소수이면서 팰린드롬인 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.

 

펠린드롬이란? 

- 뒤집은 수와 일치하는 수

예) 121, 34543

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000)

입력 예제

// input
31

// ans
101

 

Tips

1. 시간 제한이 2초이고 N의 범위가 최대 1,000,000이므로 시간 초과에 어느정도 자유롭다.
2. √N 이하의 수에서 나누어떨어지지 않으면 N은 소수이므로 √N 까지만 약수인지 찾으면 된다. (정답코드에서는 N/2 범위로 찾았지만 통과했다)

 

정답 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool isFelindrom(int N) {
	
	string str, str_reversed;
	str = str_reversed = to_string(N);
	
	reverse(str_reversed.begin(), str_reversed.end());

	if (str == str_reversed) return true;

	return false;
}

bool isPrime(int N) {

	if (N == 1) return false;

	for (int i = 2; i <= N / 2; i++) {
		if (N % i == 0) return false;
	}

	return true;
}

int main(void) {

	int N;

	cin >> N;

	while (1) {
		if (isFelindrom(N) && isPrime(N)) break;
		N++;
	}

	cout << N << '\n';

	return 0;
}

 

참고