소수를 판별하는 알고리즘

소수란 무엇인가요?

소수는 1과 자기 자신 이외에는 나누어 떨어지지 않는 자연수를 말합니다. 쉽게 말해, 약수가 1과 자기 자신뿐인 수입니다. 소수를 판별하는 알고리즘을 통해 주어진 수가 소수인지 아닌지를 확인할 수 있습니다.

소수 판별 알고리즘 - 에라토스테네스의 체

에라토스테네스의 체는 주어진 범위 내에서 소수를 찾는 효율적인 알고리즘입니다. 아래는 에라토스테네스의 체 알고리즘의 동작 순서입니다.

1. 2부터 시작하여 차례로 배수들을 지워나갑니다.
2. 이미 지워진 수는 건너뛰고, 지워지지 않은 수를 찾습니다.
3. 해당 수의 모든 배수를 지웁니다.
4. 범위 내 모든 수를 확인할 때까지 위 과정을 반복합니다.

에라토스테네스의 체 알고리즘을 통해 소수를 판별할 경우, 해당 범위 내의 모든 소수를 빠르게 찾을 수 있습니다.

소수 판별 알고리즘의 구현

아래는 파이썬으로 구현한 에라토스테네스의 체 알고리즘 예시입니다.

def sieve_of_eratosthenes(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False

    for i in range(2, int(n**0.5)+1):
        if prime[i] == True:
            for j in range(i*2, n+1, i):
                prime[j] = False

    return [x for x in range(n+1) if prime[x] == True]

위 함수의 입력 값으로 판별하고자 하는 최대 범위인 n을 받습니다. prime은 n+1개의 원소를 가진 리스트로, 인덱스의 수가 소수인지를 나타내는 변수입니다. 초기값으로 모든 원소는 True로 설정되어 있습니다.

range(2, int(n**0.5)+1)은 시작값과 종료값을 정하여 반복문을 돌리는 구문입니다. 여기서 int(n**0.5)+1은 n의 제곱근보다 작은 수까지만 반복문을 실행하도록 함으로써 효율성을 높입니다.

알고리즘을 정리하면 다음과 같습니다.

1. prime 리스트에서 인덱스 0과 1의 값을 False로 변경하여 소수가 아님을 표시합니다.
2. range(2, int(n**0.5)+1)에서 순차적으로 값을 가져옵니다.
3. 현재 수(i)가 소수인 경우, 해당 수의 모든 배수를 False로 변경합니다.
4. 순차적으로 모든 수에 대해 위 과정을 반복합니다.
5. prime 리스트에서 값이 True인 인덱스만 모아서 소수 리스트를 구합니다.

마무리

에라토스테네스의 체 알고리즘은 주어진 범위 내에서 소수를 찾는 가장 효율적인 방법 중 하나입니다. 이 알고리즘을 사용하면 임의의 수가 소수인지 아닌지를 빠르게 판별할 수 있습니다.