[백준] 2023 신기한 소수 - 파이썬

문제

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

 

 

---

풀이

 

예전 카카오 코테에서 얻은 팁..

에라토스테네스의 체는 조건제한을 잘 보고 사용해야 한다!

 

이 문제에서는 n이 8 이하였기 때문에 자칫하면 시간복잡도가 너무 높아질 수 있을 것 같았다.

게다가 '신기한 소수'를 구하는 문제이기 때문에 조건으로 연산 수를 줄일 수 있었다.

 

그래서 모든 소수를 구하는 에라토스테네스의 체를 사용하는 대신 isPrime으로 소수 여부를 체크했다.

 

또한 신기한 소수이기때문에 한자리 수 중 소수가 아닌 수를 앞자리로 하는 두자리 수의 소수는 구할 필요가 없다.

한 자리 소수는 2, 3, 5, 7 뿐이다.

41 -> 이렇게 앞자리 수가 2, 3, 5, 7이 아닌 수를 계산할 필요가 없어진다.

 

이렇게 뽑은 두 자리 신기한 소수에서 세 자리 소수를, 세 자리에서 네 자리를 쭉쭉 n까지 계산하면 된다.

 

import math

n = int(input())

bprime = [2, 3, 5, 7] #이전 자리 수 소수
aprime = [] # +1자리 수 소수
tail = [1, 3, 7, 9] #소수의 끝자리는 1,3,7,9만 올 수 있음

def isPrime(num):
    if num%2 == 0:
        return False
    for i in range(3, int(math.sqrt(num))+1, 2): #3부터 num의 제곱근까지 +2씩
        if num%i == 0:
            return False
    return True

for i in range(n-1):
    while bprime:
        b = bprime.pop()
        for t in tail:
            if isPrime(b*10+t):
                aprime.append(b*10+t)
    bprime = aprime #다음 연산을 위해 바꿔치기
    aprime = []

bprime.sort()
for b in bprime:
    print(b)