소수 찾기 - 에라토스테네스의 체

처음 접했을 땐 뭔소린지 하나도 모르겠었는데..

약수 찾기를 이해하고 나니 갑자기 이해되기 시작

 

예시

1부터 n까지의 수 중 소수를 찾아야 할 때 작은 수 부터 시작해 본인의 배수를 걸러낸다.

그럼 소수밖에 남지 않는다.

예.. 이렇게요....

 

이 개념을 처음 접했을때는 이걸 언제까지 하느냐가 아리송했었는데

약수 찾기와 마찬가지로 본인의 제곱근까지다.

그러니까 왜 제곱근까지냐고!!! 가 죽어도 이해 안됐었는데

 

제곱근까지만 확인하면 되는 이유

1~100을 예시로 들었을 때 제곱근인 10까지만 배수를 걸러내면 그 뒤로 11, 13, 17같은 수들이 남게 된다.

왜 11의 배수는 안걸러내냐면

 

1. 22, 33, 44, 55...99 같은 애들은 이미 앞에서 2, 3, 5 같은 작은 친구들이 처리해줬고

2. 11*10인 110같은 경우 이미 1~100의 범위에서 벗어나있다.

 

 

파이썬 코드로 구현 예시

def sieve_of_eratosthenes(n):
    # 모든 수를 소수로 가정하고 True로 초기화
    is_prime = [True] * (n + 1)
    
    for i in range(2, int(n**0.5) + 1): # n의 제곱근까지
        if is_prime[i]: # i가 소수가 맞다면
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False # 배수들을 모두 False처리

    # 소수 리스트 반환
    prime_numbers = [p for p in range(2, n + 1) if is_prime[p]]
    return prime_numbers