[ baekjoon ] 신기한 소수 2023번 ( python )

문제

백준 2023 신기한 소수 풀이 ( 파이썬 )

www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

풀이

처음에는 에라토스테네스의 체를 이용해서 시도했으나 시간초과가 났다...

 

• 시간 초과 코드

m=int(input())

a = [False,False] + [True]*(10**m-1)
primes=[]

for i in range(2,10**m//2):
    # if a[i]:
    #     primes.append(i)
    for j in range(2*i, 10**m, i):
        a[j] = False

def judge(num):
    while len(num):
        num=int(num)
        if not a[num]:
            return False
        num=str(num)
        num=num[:-1]
    return True


def sol(num):
    for i in range(num,num*10):
        if judge(str(i)):
            print(i)

    return

sol(10**(m-1))

 

그래서 그냥 소수 판별로 하는게 좋다고 생각해 바꿈

• 정답 코드

n=int(input())

# 소수 판별
def isPrime(a):
    if(a<2):
        return False
    for i in range(2,int(a**0.5)+1):
        if(a%i==0):
            return False
    return True

def dfs(num):
	# 목표 길이 도달 시 멈춤
    if len(str(num))==n:
        print(num)
    else:
        for i in range(10):
            temp=num*10+i
            if isPrime(temp):
                dfs(temp)

dfs(2)
dfs(3)
dfs(5)
dfs(7)