문제

---

A prime number is an integer greater than 1 which is only divisible by the integers 1 and itself, and no other positive integers. A palindromic number is one that is the same when read forwards or backwards, when written with no leading zeros. A palindromic prime is a prime number that is also a palindrome. The first few palindromic primes are 2, 3, 5, 7, 11 and 101.

Given two integers, L and H, determine the number of palindromic primes that are between L and H, inclusive.

입력

---

The first and only input line will contain two space separated integers: L (2 ≤ L ≤ 1012) and H (L ≤ H ≤ 1012), the lower and upper bounds (inclusive) for the search.

출력

---

Print a single integer on a line by itself: the number of palindromic primes between L and H, inclusive.

예제 입출력

예제 입력 1 
2 101

예제 출력 1 
6

예제 입력 2 
238 382

예제 출력 2 
3

Code

import random
def miller(m):
    if m == 2 or m == 3:
        return True
    if m <= 1 or m % 2 == 0:
        return False
    r, d = 0, m - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(5):
        a = random.randint(2, m - 1)
        x = pow(a, d, m)
        if x == 1 or x == m - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, m)
            if x == m - 1: break
        else : return False
    return True

def palindrome(N) : 
    intN = int(N)
    lenN = len(N)
    if intN <= 8 :
        r = intN + 1
    elif N.count("9") == lenN :
        r = intN + 2
    elif lenN % 2 == 0 :
        r = N[:lenN//2] + N[:lenN//2][::-1]
        while int(r) <= intN :
            r = str(int(N[:lenN//2])+1) + str(int(N[:lenN//2])+1)[::-1]
    else :
        a = N[:lenN//2]
        b = N[lenN//2:lenN//2+1]
        r = a + b + a[::-1]
        while int(r) <= intN :
            b = str(int(b) + 1)
            if int(b) >= 10 :
                b = '0'
                a = str(int(a) + 1)
            r = a + b + a[::-1]
    return r

L, H = map(int,input().split())
num = L-1
palin = []
primes_palin = []
while num < H :
    palin.append(palindrome(str(num)))
    num = int(palin[-1])
    if miller(num) and num <= H : primes_palin.append(num)
print(len(primes_palin))

풀이

이 문제는 밀러라빈 소수 판별법을 이용한 문제는 맞지만 포인트는 팰린드롬 생성이라고 생각한다. 내가 생각한 방법은 다음 팰린드롬 수를 생성하는 함수를 만들어 도는 것이다.

예를 들어, L이 100이라고 하자.
100의 다음 팰린드롬 수는 101이다.
1. 100의 다음 팰린드롬 수인 101을 구한다.
2. 그럼 이 수가 소수인지 아닌지 밀러 라빈 소수 판별법을 이용해 판별하 고 소수라면 리스트에 넣어준다.
3. 또 다시 리스트의 -1번째 값을 다음 팰린드롬으로 만들어주는 함수에 넣어 101의 다음 팰린드롬 수를 구한다 (... 이런식으로 -1번째 값이 H보다 작을 때까지 무한 반복한다.)

이런 방법을 쓰면 수가 더 커질수록 획기적으로 연산 횟수가 줄어들 것이다.