알고리즘 OJ - 메타데이터

회문질수
시한: 1000ms 메모리 제한: 10000K 총 시한: 3000ms
설명:
151은 하나의 질수이자 하나의 회문수이기 때문에 (왼쪽에서 오른쪽으로 보는 것과 오른쪽에서 왼쪽으로 보는 것은 같다) 151은 회문질수이다. 프로그램을 써서 범위를 찾아낸다[a, b](5<=a
입력:
첫 번째 줄의 두 정수: a와 b.
출력:
회문질의 목록을 한 줄씩 출력합니다.
샘플 입력:
5 500
출력 예제:
5 7 11 101 131 151 181 191 313 353 373 383
본 문제는 제가 비교적 긴 시간을 했고 회문의 질수가 간단하다고 판단했습니다. 즉, isPrime()입니다.isSyS();두 개의if문장을 끼워 넣으면 실현할 수 있지만 제출한 후에 시간이 복잡하고 높다는 것을 발견했다. 그러므로 소수를 판단하는 복잡도가 비교적 높기 때문에 먼저 회문을 판단한 다음에 소수를 판단해야 한다. 그리고 회문의 판단에 대해 여러 개의 숫자를 수조로 저장한 다음에 비교를 하는 것도 비교적 지루하다. 회문 수의 정반값이 같다고 생각하면 코드를 다음과 같이 변경한다.

#include
#include
using namespace std;

bool isPrime(int val){
    int q;
    for(q = 2; q <= sqrt(val); q++){
        if(val % q == 0){
            return false;
        }
    }
    if(q > sqrt(val)){
        return true;
    }
}

bool isSyS(int val){
    int a[11];
    int i = 0;
    int reverseVal = 0;
    int valrecord = val;
    while(true){
        reverseVal = reverseVal*10 + valrecord%10;
        valrecord = valrecord/10;
        if(valrecord < 1){
            break;
        }
    }
    if(reverseVal == val){
        return true;
    }else{
        return false;
    }
}

int main(){
    int a, b;
    cin >> a >> b;
    int i;
    for(i = a; i < b; i++){
        if(isSyS(i)){
            if(isPrime(i)){
                cout << i << endl;
            }
        }
    }
}

그러나 제출 발견은 시간의 복잡도 요구를 충족시키지 못하고 재심식 발견[a,b](5<=a
인터넷에서 회문소수의 성질을 검색해 보면 4위, 6위, 8위의 회문수가 모두 소수가 아니라는 것을 알 수 있다.이로써 일부 데이터를 제거할 수 있고 두 자릿수 안에 세 개의 회문소수만 있기 때문에 세 자릿수 이내의 소수는 표를 쳐서 계산하고 나머지는 숫자에 따라 선생이 회문수로 다시 소수의 판단을 한다.코드는 다음과 같습니다.

#include
#include
using namespace std;

bool isPrime(int val){
    int q;
    for(q = 2; q <= sqrt(val); q++){
        if(val % q == 0){
            return false;
        }
    }
    if(q > sqrt(val)){
        return true;
    }
}

int getlength(int border){
    int m = 1, k = border;
    while(k > 9){
        k /= 10;
        m++;
    }
    return m;
}

int main(){
    int a, b;
    cin >> a >> b;
    int p, q;
    p = getlength(a);
    q = getlength(b);
    if(p <= 1 && q >=1){//  
        if(a <= 5 && b>=5){
            cout << 5 << endl;
        }
        if(a <= 7 && b >= 7){
            cout << 7 << endl;
        }
    }

    if(p <= 2 && q >=2){//  
        if(a <= 11 && b >= 11){
            cout << 11 << endl;
        }
    }

    if(p <= 3 && q >= 3){//  
        int x,y;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                temp = x*100 + y*10 + x;
                if(temp >= a && temp <= b){
                    if(isPrime(temp)){
                        cout<= 5){//  
        int x,y,z;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                for(z = 0; z <= 9; z++){
                    temp = x*10000 + y*1000+ z*100 + y*10 +x;
                    if(temp >= a && temp <= b){
                        if(isPrime(temp)){
                            cout<= 7){//  
        int x,y,z,t;
        int temp;
        for(x = 1; x <= 9; x += 2){
            for(y = 0; y <= 9; y++){
                for(z = 0; z <= 9; z++){
                    for(t = 0; t <= 9; t++){
                        temp = x*1000000 + y*100000 + z*10000 + t*1000 + z*100 + y*10 + x;
                        if(temp >= a && temp <= b){
                            if(isPrime(temp)){
                                cout<