Palindromic Primes

• 범위 안의 회문 소수의 갯수를 찾는 문제.
  • 1990의 어려운 버전.
• 회문수이면서 소수인 것들을 찾으면 되는데, 두가지 방법이 있을 수 있다.
• 먼저, 범위안의 소수들을 모두 구한다음에, 각각이 회문수인지 확인하는 방법이다.
  • 어떤 수가 회문수인지 확인하는 것은, O({자릿수})만큼의 연산이 걸린다. 엄밀하게는 결국 O(logn)이지만, 최대 12자리이므로 거의 상수라고 봐도 된다.
  • 하지만 이 방법은 범위 안의 소수들을 모두 구하는 것에 O(nloglogn) 정도가 걸린다. 결국 n이 최대 10^12인 이 문제에서는 쓸수 없다.
• 다음은, 반대로 범위 안의 회문수들을 모두 구한 다음에, 각각이 소수인지 확인하는 방법이다.
  • d자리 회문수를 만들려면 d/2자리 수를 뒤집어서 이어붙이면 된다. 그러면 회문수의 갯수는 대충 O(sqrt(n))개라고 생각할수 있다. 회문수를 모두 만드는 것도 O(sqrt(n)).
  • 어떤 수가 소수인지 판별하는 것은 O(logn)
  • 총 O(sqrt(n)*log(n)) 정도로 돌아간다
• 여기에 추가적인 팁들이 있다.
• 짝수길이의 회문수는 모두 11의 배수이므로, 11을 제외하고는 모두 합성수이다. 따라서 홀수길이의 회문수에 대해서만 체크하면 된다.
• 홀수길이의 회문수를 만들 때에는 두가지 방법을 생각할수 있다. d자리 숫자를 가지고 (2d-1)자리의 회문수를 만들려면, 원래 수를 앞에 놓고 뒤집은 수를 뒤에 붙이는 방식으로 만들수도 있고, 뒤집은 수를 앞에 놓고 원래 수를 뒤에 붙이는 방법으로도 만들수도 있다.
  • 123 을 12321로 만드는 방식과, 32123로 만드는 방식이 있다는 말이다
  • 첫번째 방식으로 만드는것이 훨씬 간단한데.. 이유는 두번째 방법으로 할때는 원래 수가 0으로 끝날때에는 제외시켜줘야 하고, 대신 10001 과 같은 회문수를 만들려면 원래수를 001 처럼 표현해줘야 하는 등 신경쓸게 더 많아지기 때문이다. 또한 첫번째 방식으로 만들면 회문수가 정렬된 순서로 생성된다는 장점도 있다.
  • 하지만 이 문제에서는 두번째 방법이 유리한 점도 있는데, 이 문제에서는 소수가 될수 없는 회문수는 제외해도 되니까, 홀수인 회문수만 만드는 편이 더 효율적이다. 홀수인 회문수만 만들려면 수를 2씩 증가시켜서 만들면서 두번째 방식으로 만드는 편이 간단하다..
  • 그래서 어떤 방식으로 만들지 고민을 조금 했었는데.. 그냥 로직을 조금 바꾸더라도 첫번째 방식으로 짜는게 더 간편할거 같다고 결정했다.
  • 실제 실행 시간은 모든 회문수를 만들었을때에는 8500ms 정도가, 홀수인 회문수만 만들었을때에는 6000ms 정도가 걸렸다
• 수행속도 1등의 코드는, 내 코드보다 두배 이상 빠르다. 코드를 보니 소수 판별할때 밀러-라빈 테스트 대신에, 베이스를 2로 하는 페르마 테스트를 사용했다. 이것을 사용할수 있는 이유는, 범위 안의 회문 소수들 중에서는 1개의 예외만을 제외하고는 모두 페르마테스트로 판정이 가능하다고 한다. (근데 이것을 확인하려면.. 미리 페르마 테스트를 다 돌려서 밀러-라빈 테스트 결과와 비교해보는 수밖에 없었지 않나 싶은데..)
  • https://ii-eugene-ii.github.io/Post/Post01000/00008.html

"""Solution code for "BOJ 25821. Palindromic Primes".

- Problem link: https://www.acmicpc.net/problem/25821
- Solution link: http://www.teferi.net/ps/problems/boj/25821

Tags: [Math] [Number theory]
"""

from teflib import numtheory


def main():
    L, H = [int(x) for x in input().split()]

    answer = 0
    if L <= 2 <= H:
        answer += 1
    if L <= 11 <= H:
        answer += 1
    beg = size = 1
    while beg * size <= H:
        for i in range(beg, beg + size):
            s = str(i)
            n = int(s + s[-2::-1])
            if L <= n <= H and numtheory.is_prime(n):
                answer += 1
        beg += size * 2
        if beg > size * 10:
            beg = size = size * 10

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.is_prime