[백준알고리즘] 2023번: 신기한 소수 -Python

[백준알고리즘] 2023번: 신기한 소수 -Python

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

2023번: 신기한 소수

처음에는 에라토스테네스의 체를 이용해서 10**8만큼의 리스트를 만들었었다.

만들고 보니 10**8만큼을 미리 검사하느라 시간이 굉장히 오래 걸렸었다.

 

그래도 정상동 작은 해서 제출을 했더니 메모리 초과가 떴다. 낼 때도 그냥 내봤던 거라 메모리 초과를 보고메모리 제한을 보니 4MB밖에 안 주어졌다.

 

그래서 어쩔 수 없이 소수 판별하는 방법으로 바꾸었다. 수를 만들어보고 제곱근까지 나눠서 나눠 떨어트리는 수가 존재하면 해당 수는 소수가 아니게 되는 성질을 이용했다.

여기서는 제곱근까지의 모든 수를 사용했지만 제곱근까지의 모든 '소수'만 나눠보면 된다.

 

def find(num):
    for i in range(2, int(int(num)**0.5)+1):
        if int(num) % i == 0:
            return
            
    if len(num) == n:
        print(num)
        return

    for p in prime:
        find(num+p)
    
n = int(input())
start = ['2', '3', '5', '7']
prime = ['1', '3', '7', '9']
for s in start:
    find(s)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다