[Algorithm] 쉽게 이해하는 소수찾기 알고리즘 : 에라토스테네스의 체(파이썬)

전체 Contents

 

 

본 글에서는 전체 큰 틀을 잡기 위한 기초적인 에라토스테네스의 체를 구현하였습니다.

 

 

크게 에라토스테네스의 체가 무엇이고 왜 나왔으며 파이썬 코드로 어떻게 표현하는지에 초점을 맞춰 글을 작성하였고

글을 읽어 나갈 때 컴퓨터의 자원에 대한 관점으로 읽어나가시면 됩니다. :)

 

 

 

 

 

 

 

 

Contents

---

 

* 에라토스테네스의 체

 

ㄴ 개념이 뭔데?

 

ㄴ 왜 나오게 되었을까?

 

ㄴ 어떻게 표현할 것인가?(파이썬)

 

 

 

 

 

 

 

 

 

에라토스테네스의 체 란 무엇인가?

---

 

1) 이론

 

: 내가 원하는 수까지 소수를 빠르게 찾는 알고리즘

 

 

 

 

 

 

 

 

소수란 무엇인가?

---

 

 

 

 

: 2보다 큰 자연수에 대해, 1과 자기 자신 이외의 다른 양의 정수로 나누어 떨어지지 않는 수(1은 소수가 아니다)

Ex) 2,3,5,7,11.....

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2) 왜 에라토스테네스의 체라는 개념이 나오게 됐을까?

 

: 문제가 나오게 된 Worst Case를 보는 것이 이해하기 쉽다.

 

 

 

 

 

 

 

< 기존의 소수를 찾는 방식>

---

 

 

: 주어진 n을 2부터 (n-1)까지의 모든 수로 나누어 보는 것이다. 만약 2부터 n-1까지의 모든 자연수로 나누었을 때 하나라도 떨어지게 된다면 n은 소수가 아니다.

 

def is_prime(n):
    
    for i in range(2, n):
        
        if n % i == 0:
            return False
        
    return True

 

 

 

 

하지만 이런 방식은 매우 비효율적일 수밖에 없다.

 

 

만약 n이 100,000,000이라면?..

2부터 99,999,999까지의 모든 수에 대하여 하나씩 나누어야 하기 때문에 자원적 낭비가 매우 클 수밖에 없다.

 

 

그래서 에라토스테네스의 체라는 소수 찾기의 알고리즘을 사용하게 된 것이다.

 

 

 

 

 

 

 

3) 에라토스테네스의 체로 어떻게 소수를 찾을 것 인가?

 

 

만약 n이하의 소수를 찾고 싶다.

 

n이 2 이상 루트 n이하의 자연수 들 중 하나라도 나누어 떨어지게 되면 그 수는 소수가 아니다

 

반면

 

n이 2 이상 루트 n이하의 자연수로 나누어 떨어지지  않으면 그 수는 소수다.

 

 

 

 

 

 

 

위의 말이 무슨 말이지? 그리고 왜 루트 n이하의 자연수까지 일까?

---

 

기본적으로

 

소수인 자연수 n = 루트 n * 루트 n

소수가 아닌 자연수 n = 루트 n * 루트 n = p * q

 

라고 가정할 때 p * q 꼴로 나타내 지게 된다면 주어진 n은 소수가 아니다.

 

Ex)

12 = 루트 12 * 루트 12 = 2 * 6

 

이때 상관관계를 봐야 하는데 아래 그림을 참고하면 된다.

 

 

 

 

(1)

 

 

 

 

(2)

 

 

루트 n > p,

루트 n < q

 

2가지 조건 중 활용 가능한 건, 바로 첫 번째의 조건이다.

 

루트 n > p 

 

만약 루트 12의 경우로 다시 예를 들자면

 

루트 12보다 작은 p 즉 2,3이 된다.

 

 

이때 루트 n이하의 자연수 들중 2,3으로 주어 진수 12는 나누어 떨어지기 때문에, 12는 소수가 아니다.

 

12의 경우는 루트n 이하의 자연수 2,3 모두 떨어지므로 소수가 아니다.

13의 경우는 루트n 이하의 자연수 2,3 모두 떨어지지 않으므로 소수다.

14의 경우는 루트n 이하의 자연수 2,3 중 2 하나로라도 떨어지므로 수수가 아니다.

15의 경우는 루트n 이하의 자연수 2,3 중 3 하나로라도 떨어지므로 소수가 아니다.

16의 경우는 루트n 이하의 자연수 2,3,4중 2와 4의 경우로 떨어지므로 소수가 아니다.

 

 

 

 

 

 

 

 

 

에라토스테네스의 체를 파이썬 코드로 어떻게 구현할 것인가?(for문, while문)

---

0과 1은 소수가 아니기 때문에 False 처리를 해놓고 이외의 모든 값들은 True 처리를 해놓는다!

 

 

 

import math
 
n = 100
 
is_prime = [True for i in range(n + 1)]
 
is_prime[0] = False
is_prime[1] = False
 
for loop in range(2, int(math.sqrt(n))) :
  if is_prime[loop] == False :
    continue
 
  for loop2 in range(2 * loop, n + 1, loop) :
    is_prime[loop2] = False
 
 
 
# print
for i in range(1, n + 1) :
  if (is_prime[i] == True) :
    print(str(i))

 

 

 

 

왜? 루트값인지 궁금하다면? 아래 2가지의 코드를 먼저 살펴보고 위를 학습하실것을 권장 드립니다. :)

 

 

 

▼ 아래의 코드는 루트값까지 검사를 함으로써 시간 복잡도의 성능이 향상된 소수판별 알고리즘

 

* for문

 

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

 

 

 

 

 

* while문

 

def is_prime(n):
    idx = 2
    
    while(idx*idx<=n):
        if(n % idx == 0):
            return False
        
        idx += 1
    
    return True

 

: while문의 경우 idx*idx <= n에 집중할 필요가 있다.

 

idx^2 <= n

 

idx <= 루트 n

 

이 성립하지 않는가?