[백준/Python] 2023. 신기한 소수

2023. 신기한 소수

2023번: 신기한 소수

• 백트래킹

처음에는 에라토스테네스의 체를 사용하는 문제일 것이라고 생각했다.

가능한 수의 범위가 컸기 때문이다. (10**8)

하지만 사용 가능한 메모리가 4MB 뿐이라서, 가능한 범위만큼의 배열을 선언할 수는 없는 문제였다.

 

순차 탐색을 통해 소수를 판별하는 가장 빠른 방법

소수란, 1과 자기 자신 이외의 약수를 갖지 않는 수를 말한다.

 

약수의 개수를 구하는 것이 아니라, 단순 소수를 판별하는 경우에는
자기 제곱근(내림) 까지만 순차 탐색으로 확인하면 된다.

 

그 이후 수부터는 해당 숫자를 도출하기 위해 보다 작은 수와 곱해져야 하는데,
이는 이미 앞에서 탐색한 경우에 해당하기 때문이다.

 

코드 (Python)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e8))

def get_prime(l, current):
    if l == n:
        print(current)
        return
    for i in range(10):
        new = current*10 + i
        if is_prime(new):
            get_prime(l+1, new)

def is_prime(number):
    for i in range(2, int(number**0.5)+1):
        if number % i == 0:
            return False
    return True

n = int(input())
for i in [2, 3, 5, 7]:
    get_prime(1, i)