728x90
[백준알고리즘] 2023번: 신기한 소수 -Python
https://www.acmicpc.net/problem/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)
잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다
728x90
'algorithm > 백준알고리즘' 카테고리의 다른 글
[백준알고리즘] 2163번: 초콜릿 자르기 -Python (0) | 2020.04.06 |
---|---|
[백준알고리즘] 3109번: 빵집 -Python (0) | 2020.04.05 |
[백준알고리즘] 1799번: 비숍 -Python (0) | 2020.04.05 |
[백준알고리즘] 1339번: 단어 수학 -Python (2) | 2020.04.04 |
[백준알고리즘] 2661번: 좋은수열 -Python (0) | 2020.04.04 |