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

문제 파악

1. 최대 계산 범위는 8자리까지, 제한 시간 2초(파이썬은 8초)
   -> 생각보다 시간 제한은 널널한 것 같다
2. 첫번째 자리수부터 한 자리씩 늘려갈 때마다 모두 소수여야 한다
   -> 생각보다 고려해야할 부분은 적을 것 같다. 한자리 수일 때 2를 제외하면 짝수는 고려하지 않아도 되니까.
3. 소수는 어떻게 구할까
   -> 2 ~ $\sqrt{n}$까지 수로 나눠보기
   -> 아니면 최대 자리수까지 소수를 구해놓고 리스트에 인덱스로 접근하면 탐색 시간은 O(1)이니까 효율적이지 않을까. 처음에 소수 구하는 것만 시간이 좀 더 걸릴듯

코드

import math
from collections import deque

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

def main():
    n = int(input())
    max_num = 8 * int(math.pow(10, (n - 1)))
    ans = []
    for i in [2, 3, 5, 7]:
        q = deque([])
        q.append(i)
        max_len = int(max_num / 8)
        while q:
            tmp = q.popleft()
            if is_prime(tmp):
                if not (tmp // max_len):
                    for j in [1, 3, 7, 9]:
                        q.append((tmp * 10) + j)
                else:
                    ans.append(tmp)
    for i in ans:
        print(i)

main()

리뷰

1. 처음에 소수를 다 구하고 시작하니까 메모리 초과가 뜨더라. 역시 천만자리 숫자까지 다루는 문제에서 소수를 다 구해놓고 시작하려니 메모리가 초과된 것 같다.

prime = [True for _ in range(max_num)]
prime[0:2] = (False, False)
for i in range(int(math.sqrt(max_num)) + 1):
    if prime[i]:
        j = i * i
        while j < max_num:
            prime[j] = False
            j += i

그래서 첫번째 방법인 2 ~ $\sqrt{n}$로 나눠보는 방식으로 소수를 판단하였다.

2. pow, sqrt의 반환값은 float이었다
   max_num : 첫째 자리에서 제일 큰 값으로 7이 올 수 있으니 만약 N이 3이라면 가능한 최대 값은 799가 된다. 그래서 8 * 10 ^ 3인 식으로 계산
   $\sqrt{n}$ : 합성수라면 두 수의 곱으로 표현되고, 두 수는 대칭이므로 최대 $\sqrt{n}$까지 될 수 있다. 그래서 $\sqrt{n}$까지만 나눠봐도 된다
3. 오름차순으로 계산되어야해서 deque사용함.
4. ans로 저장 안 하고 바로 값을 출력해도 될 듯
5. 첫번째 자리에 올 수 있는 소수는 2,3,5,7, 그리고 그 후로 올 수 있는 수는 1,3,7,9라서(짝수 빼고 5는 무조건 5의 배수가 되기 때문) for문 저렇게 돌렸다.
6. main 함수로 감싼 이유 : 함수로 전체를 감싸면 조금 더 빨라진다. 모든 변수가 로컬로 저장되는데, 이때 연산이 더 빨라진다고한다. Cpython의 특징이라함. PyPy에서는 상관 없으려나