알고리즘 - Python / 백준 - 2023번 : 신기한 소수

2023번: 신기한 소수 (acmicpc.net)

2023번: 신기한 소수

 

---

풀이

• n ( 1 ~ 8 ) 자리 수를 왼쪽에서부터 1,2,... n 자리로 잘라 읽었을 때 모두 소수인 수를 신기한 소수라고 하고 , 입력받은 자릿수의 신기한 소수를 모두 출력하면 된다.
• 왼쪽에서 부터 잘라 읽었을 떄 모두 소수가 되야 하므로 , 기존에 있던 소수 뒤에 0 ~ 9를 붙여 다음 자릿수의 소수후보들을 만들고 그 소수후보들중에서 소수를 추려 각 자릿수 배열에 넣는 방식으로 해결하였다.
• 소수 판별은 약수의 대칭성을 이용해 x의 제곱근 까지만 판별하는 알고리즘 (시간복잡도 O(N^1/2) 을 사용하여 구현하였다.

 

import sys
import math

n = int(sys.stdin.readline())

def prime_check(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

hold = [0,1,2,3,4,5,6,7,8,9]
prime = [[2,3,5,7],[],[],[],[],[],[],[]]
for i in range(1,8):
    for t in hold:
        for k in prime[i-1]:
            if prime_check(int(str(k)+str(t))):
                prime[i].append(int(str(k)+str(t)))
prime[n-1].sort()
for i in prime[n-1]:
    print(i)

---