백준 BOJ 1747 - 소수&팰린드롬

소수이면서 팰린드롬인 수를 구하는 문제.

문제에서 요구하는대로 소수인 수들을 미리 구해놓고,

이들 중에서 팰린드롬인 수를 찾으면 된다.

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

1747번: 소수&팰린드롬

 

소수의 판정은 에라스토테네스의 체 방법을 활용했다.

	sleve[0] = 1;
	sleve[1] = 1;
	for(int i=2; i<2000000; i++){
		if(sleve[i]) continue;
		for(int j=i+i; j<2000000; j+=i) sleve[j] = true;
	}

sleve[k]는 k가 소수일때 0이고, k가 합성수일때 1이다.

반대로 저장하는편이 소스코드 길이가 짧고 작성하기가 편해서 나는 저렇게 다루는데

편한대로 해주면 될것 같다.

 

입력의 범위가 100만이라고 해서 단순히 100만까지만 구하면

아마 WA를 받지 싶다.

입력이 100만으로 들어오는 경우 100만보다 큰 소수들에서 찾아내야하기때문에

소수 및 팰린드롬 계산을 좀 넉넉하게 해둬야 한다.

대략 200만 안에는 있겠지 싶어서 나는 200만으로 했다.

 

전체 시간복잡도는 팰린드롬인지 체크하는 과정에서 O(logN)만큼이 더붙어서

O(NlogN)이다.

200만이면 널널하게 시간내에 해결할수 있고, 말이 N에 비례하는 소스지

실제로는 훨씬 빠르게 끝낼 수 있다.

 

 

그냥 보고 구현방법이 쉽게 떠오르는 편에 속하는 무난한 문제여서

가볍게 골라서 해설해본다....

 

#include <bits/stdc++.h>
using namespace std;

int rev(int k){
	int ans = 0;
	while(k){
		ans *= 10;
		ans += k%10;
		k/=10;
	}
	return ans;
}

bool sleve[2000000] = {0};

int main(){
	
	sleve[0] = 1;
	sleve[1] = 1;
	for(int i=2; i<2000000; i++){
		if(sleve[i]) continue;
		for(int j=i+i; j<2000000; j+=i) sleve[j] = true;
	}
	
	int N;
	cin >> N;
	for(int i=N; i<2000000; i++){
		if(!sleve[i] && rev(i) == i){
			cout << i;
			return 0;
		}
	}
	return 0;
}