[ 백준 - 2023 ] 신기한 소수

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

2023번: 신기한 소수

소수를 구하는 문제  + 그래프 or 백트래킹을 통한 완전탐색 문제라고 생각했다.

처음에는 에라토스테네스의 체를 사용해서 문제를 풀었었는데 주어진 메모리가 4MB로 적어서 메모리 초과가 났다.

 

범위가 주어지고 같은 수에 대해서 여러번 소수 판별을 해야할 것 같아서 에라토스테네스의 체가 적합할 것 같았는데 메로리 초과는 예상 밖이였다.

---

[ 📌 풀이 ]

• 소수를 판별하는 방법
  • 제곱근을 이용한 방법
  • 수를 절반으로 나눠서 약수와 같은 방법으로 구하는 방법
• 자리수를 만족하는 수를 찾는 방법
  • 문자열로 캐스팅 해서 자리 수 확인
• DFS를 통해서 가능성 있는 수를 탐색

---

[ 📌 코드 - Python(메모리 초과)  ]

### 에라토네스의 채 - 메모리 초과
import math

N = int(input())
M = pow(10, N)
K = pow(10, N - 1)
prime = [True] * M
prime[0] = False
prime[1] = False

for num in range(2, M):
  # 소수가 아니면 패스
  if not prime[num]:
    continue

  # ex) num이 5라면 2 ~ 4까지 나눠서 소수인지 확인
  for idx in range(2, int(math.sqrt(num)) + 1):
    if num % idx == 0:
      prime[num] = False

  if prime[num]:
    # 에라토네스의 체
    tmp = num * 2 
    while tmp < M:
      prime[tmp] = False
      tmp += num

for num in range(len(prime)):
  if prime[num] and K <= num < M:
    tmp = K
    ans = True
    
    while tmp != 1:
      if not prime[num // tmp]:
        ans = False
      
      tmp //= 10

    if ans:
      print(num)

[ 📌 코드 - Python(Pass) ]

import math

N = int(input())

def dfs(n):
  if len(str(n)) == N:
    print(n)
  
  for add in range(1, 10, 2):
    tmp = n * 10 + add

    if is_prime(tmp):
      dfs(tmp)

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

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

---

[ 📌 결과 - Python  ]

[ Result - Python ]