[백준 2023번] 신기한 소수 (Python/파이썬)

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

2023번: 신기한 소수

문제를 처음 보면 딱 드는 생각이 에라토스테네스의 체이다. 소수는 구하는 문제로는 백준 1929번에서 에라토스테네스의 체를 활용하여 소수를 빠르게 구했었다. 

이번 문제도 똑같이 완전탐색으로 for문을 돌리면서 가능한 모든 경우를 다 에라테스테네스의 체를 이용하여 걸러내려고 했지만 시간초과가 떴다. 

조금만 생각해봐도 N = 8이면 숫자가 9천만개가 있는데 그걸다 계산하려하니 시간초과가 뜰 수밖에 없었다.

그래서 생각한건 재귀함수다. 앞자리 숫자부터 소수인 부분만 골라서 탐색하는 거다.

예를들어 N = 4라면 2는 소수이고 다음으로 1을 붙이고, 그럼 21은 소수가 아니므로 3을 붙이고, 23은 소수이므로 ....

쭉쭉 1,3,5,7,9 홀수만 뒤에 붙여서 소수를 판별하는 방법이다.

위와 같은 방법이면 N = 8이더라도 굳이 9천만개의 수를 다 구해볼 필요 없이 소수가 될거 같은 수만 에라토스테네스의 체로 걸러내므로 시간을 많이 줄일 수 있다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
def Sol():
  N = int(input())

  def prime(num):
    for i in range(2, int(num**(1/2))+1):
      if num % i == 0:
        return False
    else:
      return True
    
  def dfs(n):
    if len(str(n)) == N:
      print(n)
    else:
      for i in range(1,10,2):
        if prime(10 * n + i):
          dfs(10 * n + i)
        else:
          pass
    
  dfs(2);dfs(3);dfs(5);dfs(7)

if __name__ == "__main__":
  Sol()

 

 

글이나 코드에 대한 질문, 조언 환영합니다