백준 2023 신기한 소수 (Python)

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

2023번: 신기한 소수

뻗어 나가는 느낌으로 풀었다.

다양한 길이를 가져야 하기 때문에 함수를 이용해서 풀 수 있도록 하였다.

 

소수를 판정 할 때, 어차피 계산 한 부분은 안 할 거 같아서 굳이 에라토스테네스의 체를 쓰지는 않았다.

 

함수를 이용해서, 만약 길이가 N이라면 해당 수를 바로 출력하고 아니라면 뒤에 수를 계속 붙여주는 방법으로 풀었다.

어차피 앞 부분은 이미 소수일 테니까, 해당 수가 소수인지만 판별을 진행했다.

 

import sys

N = int(sys.stdin.readline().strip())

prime = [2, 3, 5, 7]


def is_prime(number):
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True


def wow_prime(cur_number):
    if len(str(cur_number)) == N:
        print(cur_number)
    else:
        for t in range(1, 10):
            if t % 2 != 0 and is_prime(cur_number * 10 + t):
                wow_prime(cur_number * 10 + t)


for i in prime:
    wow_prime(i)