Quiz) 에라토스테네스의 체 - 소수(Prime Number)를 찾아보자.

 

Problem

Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

정수 N이 주어집니다. 이 정수 N보다 작은 모든 소수를 찾으면 됩니다.

 

Example

Input : n =10
Output : 2 3 5 7 

Input : n = 20 
Output: 2 3 5 7 11 13 17 19

 

Approach

우선 소수에 대하여 다시 짚고 넘어가 보려 합니다.  소수란 자기 자신과 1 이외에는 다른 약수가 없는 수를 의미합니다.

그러면 우리는 어떤 수가 소수인지 아닌지 어떻게 알 수 있을까요? 모든 수에 대해서 한 번씩 나눠보면 될까요? 너무 비효율적인 방법입니다.

 

우리는 에라토스테네스의 체(Sieve of Eratosthenes)라는 방법을 통해 보다 쉽게 소수를 찾아낼 수 있습니다. 이름 그대로 체를 통해 무언가를 걸러내듯이 소수를 찾는 방법입니다.

 

1. 찾을 범위까지 수를 나열한 다음, 소수가 아닌 1을 지웁니다.
2. 1 다음으로 큰 소수인 2를 남겨두고 2의 배수를 모두 지웁니다.
3. 2 다음으로 큰 소수인 3을 남겨두고 3의 배수를 모두 지웁니다.
4. prime(n) 다음으로 큰 소수인 prime(n+1)을 남겨두고 prime(n+1)의 배수를 모두 지웁니다.
5. 더 이상 지울 수 없을 때, 남아있는 수들이 소수입니다.

wikipedia

 

 

Solution (Python)

# @Reference: https://box0830.tistory.com/384
class Sieve:
    def __init__(self, n):
        self.number = n
        self.prime = []
        self.isPrime = [True for _ in range(n + 1)]

    def sieveOfEratosthenes(self):
        self.isPrime[0] = self.isPrime[1] = False

        for i in range(2, self.number):
            if self.isPrime[i]:
                self.prime.append(i)

                j = 2
                while j * i < self.number:
                    self.isPrime[j * i] = False
                    j += 1

    def display(self):
        for primeNumber in self.prime:
            print(primeNumber, end=", ")


if __name__ == '__main__':
    givenNumber = 100000

    sieve = Sieve(givenNumber)
    sieve.sieveOfEratosthenes()
    sieve.display()

 

Review

소수 문제도 종종 응용되어 시간 복잡도 제약과 함께 시험에 나오곤 합니다. 그만큼 에라토스테네스의 체에 대하여 이번 기회에 확실히 알고 넘어가면 좋을 것 같습니다.

 

참고로 이 유명한 에라토스테네스의 체, 시간 복잡도는 O(n log(logn))입니다. 증명은 조화수열의 합, 테일러급수 등이 활용되어 다소 복잡한 편입니다. 아래 오일러의 증명한 내용을 다룬 위키 백과 문서를 첨부하며 마무리하도록 하겠습니다.

 

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

Divergence of the sum of the reciprocals of the primes - Wikipedia

 

Reference

https://www.geeksforgeeks.org/sieve-of-eratosthenes/?ref=gcse 

Sieve of Eratosthenes - GeeksforGeeks