알고리즘 - Python / 백준 - 1990번 : 소수인팰린드롬

1990번: 소수인팰린드롬 (acmicpc.net)

1990번: 소수인팰린드롬

 

---

풀이

• 팰린드롬인 수들 중 범위 내의 소수들을 출력하면 되는 문제다.
• 일단 생각해보니 범위 내의 소수를 구하고 그중에 팰린드롬을 검사할지 , 범위 내의 팰린드롬을 구하고 소수인지 판별할지 정해야 했다.
• 5 ~ 1억 사이의 소수를 구하려면 에라토스테네스로 해도 되고 , 밀러 라빈이나 루트 N 까지 숫자를 넣어 소수인지 아닌지 판별하는 방식으로 구해야 한다.
• 에라토스테네스의 체는 거의 선형 시간의 시간 복잡도를 가진다고 기억하는데 그러면 O(1억)이고 , 시간 초과가 날 것이다.
• 그러면 범위 내의 팰린드롬인 수를 곰곰이 생각해보니 , 1억보다 작은 경우이므로 4자리 + 4자리 까지가 최대 길이이다.
• 즉 for문이 최대 4자리까지만 돌려주고 그냥 뒤에 앞에 쓴 걸 또 붙여주면 되는 것이다.
• 소수를 먼저 구하는 것보다 팰린드롬을 먼저 구하는 것이 시간적으로 이득이라고 생각했다.
• 따라서 팰린드롬을 먼저 구하고 그 각각이 소수인지 아닌지 검사하는 방향으로 풀어 나갔다.
• 팰린드롬은 홀수 자릿수인 경우 일단 써주고 부족한 만큼 앞에서 따와서 붙여주기로 했다.
• 예를 들어 ,  10001이라면 3자리 수로 3+3 = 6 자리 팰린드롬 수를 만들 때 100을 써주고 앞의 2개를 뒤에 붙여 100 + 01로 만든 것이다.
• 이후 소수 판별을 해야 하는데 이 경우 그냥 밀러 라빈 알고리즘을 사용하였다.
• 밀러 라빈 소수 판별 알고리즘과 관련된 내용이나 문제는 아래 링크를 참고하자.

 

 

알고리즘 - Python / 백준 - 5615번 : 아파트 임대 (tistory.com)

알고리즘 - Python / 백준 - 5615번 : 아파트 임대

 

 

 

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

 

 

 

import sys
st,fl = map(int, sys.stdin.readline().split(" "))

pl = [5,7,11]
for idx in range(2,5):
    for i in range(10**(idx-1),10**idx):
        k = str(i)
        pl.append(int(k+k[0:idx-1][::-1]))
        pl.append(int(k+k[::-1]))

def powmod(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m

    return result

def mr(n,a):
    r = 0
    d = n-1
    while (d%2 == 0):
        r += 1
        d = d // 2
    x = powmod(a,d,n)
    if x == 1 or x == n-1:
        return True
    for i in range(0,r-1):
        x = powmod(x,2,n)
        if x == n-1:
            return True
    return False


for k in pl:
    if fl >= k >= st:
        check = 0
        if 12 < k:
            for i in [2, 3, 5, 7, 11]:
                if mr(k , i) == False:
                    break
                else:
                    check += 1
            if check == 5:
                print(k)
        else:
            print(k)
print(-1)

---