백준 1990번 - 소수인팰린드롬 ( C++ / 에라토스테네스의 체)

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

 

에라토스테네스의 체를 사용하면 간편하게 풀리는 문제...... 라고생각했으나 계속 시간초과가 나서 당황했다.

 

에라토스테네스의 체를 사용하는 방법은 두가지가 있다.

 

1. 범위 내의 소수 모두 찾아내기

 

int main(){

bool check[10000];    
    for(int i = 2; i * i < 10000; i++){
        if(check[i] == false){
            for(int j = i * i; j < 10000; j+=i){
                check[i] = true;
            }
        }
    }
}

 

2. 소수 판정하기

bool Eratos(int N){
	if(N < 2) return false;

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

 

소수 판정 또한 O(sqrt(N)) 으로 판단해낼 수 있다.

 

그렇다면 이 문제는 b가 1억까지 있기 때문에 결국 1억 * 소수 판정이 들어가서 무조건 시간초과인데 어떻게 해야할까 생각이 들었는데, 소수인 팰린드롬은 천만 이후 나오지 않는다고 한다..!!! 그래서 천만까지만 보면 된다.

 

그렇다면 시간 복잡도는 

 

천만 * 8 * Root(팰린드롬의 크기) 이다. 정확히 판별할 수는 힘들지만 천만번이 돌아도 확실히 크지 않은 시간을 소요한다. 이 문제에서 가장 중요한 것은 팰린드롬의 최대 소수는 천만이하라는 것이다.

 

#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;

bool pelcheck(string str){
    string pre, after;
    pre = str;

    reverse(str.begin(), str.end());

    after = str;

    return pre == after;
}

bool Era(int n){
    if(2 > n) return false;
    
    for (int i = 2; i <= sqrt(n); i++){
    	if(n % i == 0) 
            return false;
    }
    
    return true;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    int a, b; cin >> a >> b;

    for(int i = a; i <= 10000000; i++){
        if(b < i) break;
        if(pelcheck(to_string(i)) && Era(i)){
            cout << i << '\n';
        }
    }

    cout << -1; 
}