백준 2023 파이썬

문제

신기한소수

백준 2023

풀이

이번 풀이는 여러번 틀려서 정답을 찾아가는 과정을 서술한다.

1. 에라토스테네스의 체 사용
   소수 판별 문제라고 생각이 되어 전체 범위의 숫자를에라토스테네스의 체 방식을 이용하여 소수를 구하는 방식

N=int(input())

prime=[True for i in range(10**N)]
prime[0]=prime[1]=False
for i in range(2,10**N //2):
    for j in range(i+i,10**N,i):
        prime[j]=False

# 아리스토텔레스의 체 사용 
def check_prime(num):
    num=str(num)
    t=''
    for i in num:
        t+=i
        if prime[int(t)]==False:
            return False
    return True
for i in range(10**(N-1),10**N):
    if check_prime(i)==True:
        print(i)

메모리 초과로 인한 실패

2. 메모리 문제를 해결하기 위해 전체 소수 찾는 방식으로 구현
   시간초과가 나올 것을 예상했으나,, 혹시몰라서 구현해봤다

import math
N=int(input())
def check_prime(Num):
    if Num==0 or Num==1:
        return False
    for i in range(2,int(math.sqrt(Num))):
        if Num%i==0:
            return False
    return True

for i in range(10**(N-1),10**N):
    str_i=str(i)
    tmp=''
    check=0
    for k in range(N):
        tmp+=str_i[k]
        if check_prime(int(tmp))==False:
            check=1
            break
    if check==0:
        print(i)

역시나 시간초과

최종 풀이: 가지치기를 통해 시간초과를 줄이려는 노력 진행
가지치기 조건:
1. 1~8자리 수 중에 맨 앞은 무조건 2,3,5,7이어야한다.
2. 2번째 자리 이후부터는 무조건 홀 수 이어야한다. (짝수이면 2의배수가 됨)
(5로끝나도 5의배수가 되지만 이 부분은 생략)

import math
prime=[2,3,5,7]

N=int(input())
def check_prime(Num):
    if Num==0 or Num==1:
        return False
    for i in range(2,int(math.sqrt(Num))+1):
        if Num%i==0:
            return False
    return True
def recursive_find(num,N):
    if(len(str(num)))==N:
        print(num)
        return
    
    for i in range(1,10,2):
        #가지치기 조건 2 
        if check_prime(num*10+i):
            recursive_find(num*10+i,N)

for i in prime:
    # 가지치기 조건 1
    recursive_find(i,N)

결과 정답