소수인팰린드롬

• 기본적으로는 Palindromic Primes과 같은 문제이다. 차이점은, 갯수만 출력하느냐 모든 소수를 하나씩 다 출력하느냐와 범위의 차이.
• Palindromic Primes에서 설명했듯이, 회문수를 먼저 만들고서 각각에 소수 테스트를 하는 것이 가장 빠른 방법이지만, 범위가 작기때문에 소수 목록을 먼저 만들고서 각각에 대해서 회문 테스트를 하는 방법도 통과한다.
  • 시간은 64ms vs 464ms 로 많이 느려졌지만 코드는 더 심플하다.
• 그냥 10^8 이하의 회문소수를 전처리해서 코드에 박아놓는 것도 가능하다! 이렇게 해도 회문소수가 많지 않아서 코드 길이가 6181b밖에 안된다.

"""Solution code for "BOJ 1990. 소수인팰린드롬".

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

Tags: [Number theory]
"""

from teflib import numtheory


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

    for x in (5, 7, 11):
        if a <= x <= b:
            print(x)
    beg = size = 10
    while beg * size <= b:
        for i in range(beg, beg + size):
            s = str(i)
            n = int(s + s[-2::-1])
            if a <= n <= b and numtheory.is_prime(n):
                print(n)
        beg += size * 2
        if beg > size * 10:
            beg = size = size * 10
    print('-1')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.is_prime

"""Solution code for "BOJ 1990. 소수인팰린드롬".

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

Tags: [Number theory]
"""

from teflib import numtheory

MAX_NUM = 10_000_000


def main():
    a, b = [int(x) for x in input().split()]
    for p in numtheory.prime_list(a, min(b, MAX_NUM)):
        p = str(p)
        if p[::-1] == p:
            print(p)
    print('-1')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list