[Algorithm] 소수 구하기 - 에라토스테네스의 체

소수

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

일반 코드

소수인지 검사하는 함수(isPrime)를 만든다.
isPrime() 함수는 1을 제외하고,
2부터 해당하는 자연수까지 판별할 숫자들을 하나씩 순회하면서 소수 여부를 판별한다.
따라서, 범위가 매우 큰 경우에는 많은 시간이 소요될 수 있다.

1부터 100 사이의 소수를 구하는 파이썬 코드를 작성하면 다음과 같다.

n = 100

def isPrime(a):
	if (a < 2):
    	return False
	for i in range(2, a):
    	if (a % i == 0):
        	return False
	return True

for i in range(n+1):
	if(isPrime(i)):
    	print(i)

에라토스테네스의 체

위의 코드는 해당 수보다 작은 모든 수로 나누어 소수인지를 판단하는 방법이다.
한 개의 소수를 구할 때는 괜찮지만 해당 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.
따라서, 소수를 구할 때는 에라토스테네스의 체를 이용하는 것이 좋다.

에라토스테네스의 체

해당 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

1. 1은 소수가 아니므로 제거

2. 지워지지 않은 수 중 가장 작은 2를 소수로 채택하고,
   나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 가장 작은 3을 소수로 채택하고,
   나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 가장 작은 5를 소수로 채택하고,
   나머지 배수를 모두 지운다.

5. (반복)

에라토스테네스의 체를 파이썬 코드로 표현하면 다음과 같다.

n = 1000
a = [False, False] + [True] * (n-1)
primes = []

for i in range(2, n+1):
	if a[i]:
    	primes.append(i)
        for j in range(2*i, n+1, i):
        	a[j] = False
            
print(primes)