백준 1990 소수인팰린드롬 C++

간단한 해설

 

범위가 5~100,000,000이므로 최대 1억까지의 정수를 탐색한다.

 

O(n) 정도면 얼추 된다는 뜻이다.

 

일단 에라토스테네스의 체를 이용해서 소수를 판별한다.

 

그리고 범위 안의 소수인 수들만 팰린드롬 판별을 하면 된다.

 

팰린드롬 판별은 수를 문자열로 변환하고, reverse() 메서드를 이용해서 간단하게 비교하면 된다.

 

답

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll a,b;
	cin>>a>>b;
	vector<bool> v(b+1,true);
	v[0]=v[1]=false;
	for(ll i=2;i<=b;++i){
		if(v[i]){
			for(ll j=i*i;j<=b;j+=i){
				v[j]=false;
			}
		}
	}
	vector<ll> ans;
	for(ll i=a;i<=b;++i){
		if(!v[i]) continue;
		string tmpA=to_string(i);
		string tmpB=tmpA;
		reverse(tmpB.begin(),tmpB.end());
		if(tmpA==tmpB) ans.push_back(i);
	}
	for(int i=0;i<ans.size();++i){
		cout<<ans[i]<<"\n";
	}
	cout<<-1;
}