에라토스테네스 방식으로 거르기 전에 배열안에 숫자를 팰린드롬으로 이루어진 숫자만 넣고 걸러야 하지 않을까요?

저정도 범위면 거르는 동안 만해도 시간초과가 날거같은느낌이..

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

여기보니 6천바이트~9천바이트.. 시간복잡도를 최대한 줄였을때의 코드길이인가보네요..

팰린드롬의 개수가 생각보다 적어서 풀 수 있어요.

팰린드롬 거르는방법이 따로있나요?? 체로거르는게 훨씬빠를거같은데..

길이가 1~9인 팰린드롬의 개수는 총 2*10^2 + 2*10^2  + ... + 10^5인데  

에라토네스체가 NloglogN이더라도 10^9보다 클 수 밖에 없어서 팰린드롬을 

만드는게 더 이득이에요. 

팰린드롬은 길이가 작은 자리부터 만들어 재귀적으로 만들어 대략 O(10^6)이 

걸리게 하면 후에 소수를 체크해도 풀 수 있게되요.

아아ㅏㅇ아ㅏ 감사합니당

방금 문제 풀어봤네요

일단 팰린드롬 수는 O(루트n)번만에 구할 수 있구요

소수도 100000000까지의 수가 아닌 그 제곱근인 1~10000까지의 소수만 구하여 풀었습니다.

팰린드롬 수 구하는 힌트를 드리면 :

    '123'으로 구할 수 있는 팰린드롬 수 -> '12321' , 123321'

    이러면 1~10000까지의 숫자를 이용하여 11~1000000000까지의 팰린드롬 숫자들 집합을 만들 수 있겠지요?

    (한자리 수는 무조건 펠린드롬 수가 된다는거에 주의하세요)