글 읽기 - 1990번 메모리 초과 런타임 에러 벗어날 아이디어좀 주세요 ㅠ

junghan2503 6년 전 0

MAX를100000000으로 잡자니 메모리초과가 뜨고 0을 하나 빼니 런타임이 뜨고

다르게 푸는거같은데 방법좀 갈쳐주세요

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
 
#define MAX 10000000
int arr[MAX];
char num[10];
int main(){
    int n,b;
 
    cin>>n>>b;
    for(int i = 2; i<= sqrt((double)b);i++){
        for(int j = i+i; j<= b;j+=i){
            arr[j] = 1;
    }
    }
    arr[0] = 0;
    arr[1] = 0;
    for(int i = n; i<= b;i++){
        if(arr[i]==0){
            int k = 0;
            int bro = 0;
            int t=i;
            while(1){
                num[k++] = t%10;
                t=t/10;
                if(t==0)break;
            }
            for(int j = 0; j <= k/2; j++){
                if(num[j]!=num[k-j-1])bro=1;
            }
            if(bro == 0){cout<<i<<endl;
            }
        }
    }
     cout<<-1<<endl;
    return 0;
}

________________ 6년 전 0

1천만에서 1억까진 팰린드롬소수가 없어요.

________________ 6년 전 0

그래서 2~1천만까지 에라스토테네스의 체를 썼는데

메모리 52264KB

시간 304MS로 통과됬네요.

junghan2503 6년 전 0

감사합니다 덕분에 해결했습니다. 궁금한점은 1천만에서 1억까지 팰린드롬소수가 없다는 사실은 어떻게 아시게 되었나요?

yukariko 6년 전 0

에라토스테네스의 체로 모든 범위를 구하지 않아도 됩니다.

https://www.acmicpc.net/board/view/1065

이 글을 참고해보세요.

hongjun님의 답변의 일부를 가져와봤습니다.

--

x가 소수인지 알아보려면, 루트(x)까지 에라토스테네스 체 알고리즘으로 모든 소수를 구해놓은 뒤, x를 구해놓은 소수들로 다 나눠보다가, 안 나누어진다면 소수라고 판정할 수 있죠.

--

저도 이러한 방법으로 해결하였습니다.

________________ 6년 전 0

그냥 1~1억까지 해보니까

1천만에서 1억까지 없더군요 ㅋㅋ

junghan2503 6년 전 0

감사합니다. 새로운 사실을 알게되었네요^^

댓글을 작성하려면 로그인해야 합니다.