[Python] 소수 판별(IsPrime) 알고리즘 / 에라토스테네스의 체, 나누기

소수(Prime Number)란?

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

 

 

나누기를 통해

정의에 의해 나누기를 사용하여 구현할 수 있다.

n이라는 수가 소수인지 판별하는 코드를 구현해보자.

• 1은 소수가 아니다.
• 시간 복잡도를 위해 $\sqrt(n) + 1$까지만 탐색한다.

def isPrime(n):
    if n == 1:
        return False
    
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

print(isPrime(1))   # False
print(isPrime(11))  # True
print(isPrime(12))  # False
print(isPrime(13))  # True

 

 

에라토스테네스의 체

위의 코드는 소수를 판별할 때는 좋은 코드이지만, 모든 소수를 구할 때는 효율적인 방법이 아니다. 소수를 구하기 위해 에라토스테네스가 제안한 방법은 다음과 같다.

 

에라토스테네스의 체
: 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

출처: https://wikidocs.net/21638

1. 1은 제거한다.
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
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)