[BOJ] 1747번_소수&팰린드롬_수학 (C++)

[문제]

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

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

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

[사용 알고리즘]

수학

[풀이 핵심]

• 소수 판정 함수와 팰린드롬 판정 함수를 만들면 쉽게 해결할 수 있는 문제이다.
• N이 1 ~ 1,000,000 이라고 답이 1 ~ 1,000,000이라고 생각하면 안된다. 답은 N보다 크거나 같은 수 중에서 소수와 팰린드롬인 수기 때문이다. 따라서, for문을 돌때 N ~ 1,000,000이 아닌 더 큰수까지 돌아야한다. (나는 넉넉하게 2,000,000까지 돌았다.)

[코드]

//boj1747번 소수&팰린드롬_수학

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

using namespace std;

bool isPrime(int x) {
	if (x == 1) {
		return false;
	}
	else {
		for (int i = 2; i <= sqrt(x); i++) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}
}

bool isPalin(int x) {
	string temp = to_string(x);

	string str1 = temp;
	reverse(temp.begin(), temp.end());
	string str2 = temp;
	
	if (str1 == str2) {
		return true;
	}
	else {
		return false;
	}
}

using namespace std;

int main() {
	int N;
	cin >> N;

	for (int i = N; i <= 2000000; i++) {
		if (isPrime(i) && isPalin(i)) {
			cout << i;
			return 0;
		}
	}

	return 0;
}