에라토스테네스의 체

Goal

1. 소수 정의하기
2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기

 

소수란?

소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다!

예시)

소수 : 2, 3, 5, 7, 11, 13, 17, 19, ...

그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ...

 

 

"에라토스테네스의 체"는 언제 필요한가?

• N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다
• 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다

# 소수 찾는 함수
def get_prime(start, end):
    prime_numbers = []

    for target_num in range(start, end):
        prime_numbers.append(target_num)

        for k in range(2, target_num//2):
            if target_num % k == 0:	
                prime_numbers.pop()	# 숫자 target_num가 k로 나눠진다면 소수가 아니므로 제거
                break

    return prime_numbers

# 2에서 100까지의 숫자 중 소수 찾기
print(get_prime(2, 101))

 

• 그래서 에라토스테네스의 체를 활용하면 좋다!!

"에라토스테네스의 체"란?

• 소수를 발견 했을 때 그 소수의 배수를 모두 제외시킨다

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

1. 위 그림에서 2가 소수라는걸 발견하고 나머지 2의 배수들은 2로 나눠지기 때문에 소수가 아닌 것을 알 수 있어 제외시킨다
2. 그 다음 3이 소수라는걸 발견하고 나머지 3의 배수들은 3으로 나눠지기 때문에 소수가 아니므로 제외시킨다
3. 그 다음 5가 소수라는걸 발견하고 5의 배수를 제외시킨다
4. 그 다음 7이 소수...
5. 계속 반복...