백준 1747 소수&팰린드롬

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 소수이면서 팰린드롬 수인 숫자를 입력받은 수보다 크면서 가장작은 숫자를 출력하는 문제입니다.

 

입력이 1000000까지 가능하므로 1000000보다 큰 수중에 가장 작은 소수 까지만 구해놓으면 됩니다. 어떤 수인지 몰라서 저는 그냥 2000000까지 구했습니다. 소수는 에라토스테네스의 체로 구해 놓고 팰린드롬 수를 판별하여야 하는데 저는 먼저 소수인 수를  10으로 나눠주면서 자리수별로 벡터에 집어 넣었습니다. 그런다음 벡터의 맨앞과 끝부분을 비교하며 모두 동일하다면 소수이면서 팰린드롬 수 인것으로 판별을 하였습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
//에라토스테네스의 체 

#define MAX 2000000
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N;
	cin >> N;
	bool arr[MAX];
	vector<int> v;
	fill_n(arr, MAX, true);
	arr[0] = false;
	arr[1] = false; 
	
	for(int i = 2; i < MAX; i++) {
			if(arr[i]) {
				for(int j = i+i; j < MAX; j+=i)
					arr[j] = false;
			}			
		}
	
	for(int i = 2; i < MAX; i++) {
		int a = i;
		if(arr[i]) {
			while(a / 10 != 0) {
				v.push_back(a % 10);
				a = a / 10;
			}
			v.push_back(a);
			int len = v.size();
			for(int j = 0; j < len; j++) {
				if(j == len-j-1)
					break;
				if(v[j] == v[len-j -1])
					continue;
				else {
					arr[i] = false;
					break;
				}
			}
		}
		v.clear();
	}
	
	for(int i = N; i < MAX; i++)
		if(arr[i]) {
			cout<<i;
			break;
		}

	return 0;
}