Gidhub BE Developer

[BOJ] 1747. 소수&팰린드롬

2018-10-01
goodGid

Problem

Problem URL : 소수&팰린드롬


[1] Answer Code (18. 10. 01)

#include <iostream>
#include <cstring>
using namespace std;

int pn[2000001]; // pn is Prime Number

void prime(){
    memset(pn,true,sizeof(pn));
    pn[0] = pn[1] = false;
    for(int i=2; i<=2000001; i++){
        if(pn[i] == false)
            continue;
        
        pn[i] = true;
        for(int j=i*2; j<=2000001; j+=i){
            pn[j] = false;
        }
    }
}

int solve(int n){
    string value = to_string(n);
    int size = (int) value.size();
   
    int l = 0; // l is left
    int r = size-1; // r is right
    while (1) {
        if(l > r){
            return 1;
        }
        if(value[l] == value[r]){
            l++;
            r--;
            continue;
        }
        else{
            return 0;
        }
    }
    return 0;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    prime();
    
    for(int i=n; i<2000001; i++){
        if(pn[i] == true){
            if(solve(i)){
                cout << i << '\n';
                break;
            }
        }
    }
    return 0;
}

Review

  • 주의할 점은 N이 1,000,000이 최대인데 그 보다 큰 수중 펠린드롬은 1003001이 있다.

  • 그렇기 때문에 소수를 찾을 때 1,000,000까지 구하는게 아니라 충분히 여유를 두고 소수를 구해야한다.


Comments

Content