[Python] 파이썬 소수 구하기 알고리즘

 

그 동안 소수 구하는 문제를 만나면

항상 시간 복잡도 때문에 고통을 받았습니다.

 

그 동안은 어찌저찌 넘어왔으나

이번에는 소수 구하기 단 한 문제로 하루 종일 고통을 겪었습니다.

 

그래서 이번에는 소수 구하는 방법에 대해서 확실히

하고 넘어가야겠다는 생각이 들었습니다..

 

저번에 쓴 글  파이썬 문제해결전략에서

소수와 관련된 문제를 풀기 위해서는

 

"에라토스테네스의 체"를

알고리즘으로 구현해야할 필요성에 대해 역설했습니다.

 

그래서 저는 이번에

"에라토스테네스의 체" 개념을 이용해서

문제를 풀기 위해 시도해봤습니다.

 

---

 

 

먼저 "에라토스테네스의 체" 개념을 간략하게 설명하자면..

소수의 배수들을 제외시키는 것입니다.

 

 

비유하자면 체에 모래를 넣었을 때

고운 모래만 나오는 것처럼

 

숫자를 넣었을 때

소수만 빠져나오는 것는 것입니다.

 

 

예를 들어 소수 2의 배수인 4, 6, 8, 10...과

소수 3의 배수의 6, 9, 12, 15...를 걸러버리는 것입니다..

그러면 그 다음 숫자는 5인데요,

놀랍게도 소수입니다!

 

만약..

5가 소수가 아니라면...

 

5보다 작은 수의 배수가 5인 숫자가 있어야합니다만..

이미 5보다 작은 숫자의 배수를 다 지웠으므로

5는 1을 제외하고는 약수가 없습니다!!

 

에레토스테네스의 체 개념으로 발전하는

소수 관련 공식이 궁금하시다면..

 

 

https://blog.naver.com/ssinznday/222021868584

정수론 #3. 소수(Prime number)

 

 

이 블로그를 참고해주시면 될 것 같습니다.

필요한 정리가 다 기술되어 있습니다.

 

---

 

 

일단 제가 푼 문제는

 

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

이 문제인데요

.

.

.

먼저 결과부터 말씀드리자면

저는 "에레토스테네스의 체"를 사용해서

문제를 풀지는 못하였습니다.

 

 

그래도 제가 10번 이상 다른 코드를 사용하여 구현한

"에레토스테네스의 체" 중에서

이게 그나마 시간복잡도가 낮은 편이었습니다...

 

이 코드를 해설드리자면

result에 없는 n보다 작은 수를

먼저 answer에 넣고

그 숫자의 배수를 result에 넣었습니다.

 

이렇게 하면

에레토스테네스의 체에 걸러진 소수가

answer에 담기게 됩니다.

.

.

.

근데 왜 정답을 가져오지 않고

엉뚱한 답을 가져왔느냐고 할 수 있겠는데..

 

이 문제의 테스트 케이스가 바뀌면서

기존에 정답이었던 에레토스테네스의 체 알고리즘도

틀린 것이 되어버려서

 

정답인 에레토스테네스의 체 알고리즘을 찾을 수 없었습니다...

(무려 3페이지까지 코드 찾아봄..)

 

 

정수론에 나온 알고리즘을 통해서 풀어야할 것 같았던 문제는

오히려 엄청 간단하게 풀렸습니다...

 

 

이 문제의 답

 

 

풀었긴하지만

일단 시간복잡도가 엄청났고..

 

더 복잡해 보이는 알고리즘같은데

어떻게 문제가 풀렸는지

설명할 수도 없습니다..

 

비밀은

if all(~) 부분에 있는 것 같은데..

 

알고리즘과 자료구조에 대해서

공부할 필요성을 절실하게 느끼는 요즘입니다...

 

 

아무튼...

 

혹시라도 저 문제를

에레토스테네스의 체 개념으로 풀 수 있으신 분은

정답 좀 댓글로 남겨주시면 감사하겠습니다....

 

 

 

 

 

---

 

(추가)

 

에라토스테네스 체 알고리즘을 가져왔습니다...

 

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    p = 2
    while (p * p <= n):
        if (primes[p] == True):
            for i in range(p * p, n + 1, p):
                primes[i] = False
            p += 1
    prime_numbers = [p for p in range(2, n + 1) if primes[p]]
    return prime_numbers

 

 

이 알고리즘은 미리 n개의 True가 담긴 리스트를 만들어주고

소수가 아닌 수의 인덱스에 False 값을 넣어줍니다.

마지막에 남은 True는 소수를 의미합니다.

 

직접 원소를 넣고 지우고 하는 방식 대신에

True, False를 사용하는 방식

너무 창의적인 것 같습니다.

 

기억해놓고 언젠가는 써먹어봐야겠습니다..