백준 BOJ 1990 - 소수인팰린드롬

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

1990번: 소수인팰린드롬

입력으로 들어오는 수의 범위가 적절하게 커서

O(N) 내지 O(Nsqrt(N)) 으로는 해결할 수 없다.

 

b의 범위가 최대 1억이고 1억은 팰린드롬 숫자가 아니므로,

문제에서 요구하고 있는 "최대 8자리의 팰린드롬 수" 는

앞뒤가 똑같다는 특성 때문에 1만개보다 많지 않으므로,

 

1부터 1만까지 순회하면서 이 수가 뒤에도 반복되는 팰린드롬 수를 직접 만들어주면 된다.

나는 문자열로 변경한 후

원래 문자열과 reverse 한 문자열 둘을 더해 만들었다.

1만으로 팰린드롬 수를 만들어도 10억 1으로 INT범위를 벗어나지 않는다.

 

이렇게 만들어진 대략 M개의 수들을 순회하면서

a이상 b이하인 수들 중 소수인 수를 O(Msqrt(M)) 으로 찾아내면 된다.

M의 범위는 1만을 넘지 않아 시간 내에 해결할 수 있다.

 

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

vector<int> palin;

void make_palin(int k){
	string s1 = to_string(k);
	string s2 = s1;
	string s3 = s1;
	s3.pop_back();
	
	reverse(s2.begin(), s2.end());
	reverse(s3.begin(), s3.end());
	
	int A = stoi(s1+s2);
	int B = stoi(s1+s3);
	
	if(A <= 100000000) palin.push_back(A);
	if(B <= 100000000) palin.push_back(B);
	return 0;
}

bool is_prime(int k){
	for(int i=2; i*i<=k; i++){
		if(k%i == 0) return false;
	}
	return true;
}

int main(){
	for(int i=1; i<=10000; i++){
		make_palin(i);
	}
	
	int s,e;
	cin >> s >> e;
	sort(palin.begin(), palin.end());
	for(auto k : palin){
		if(s>k || e<k) continue;
		if(is_prime(k)){
			cout << k << "\n";
		}
	}
	cout << -1;
	return 0;
}