에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

 

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

 

이 방법은 마치 체로 치듯이 수를 걸러낸다.

 

 

코드:

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    m = int(n ** 0.5)				   # 제곱근	
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

 

소수 목록 산출은 컴프리핸션을 이용한 풀이다.

2부터 n까지 for 문을 돌리는데 sieve[i]가 True 면 리스트로 만들고 전부 숫자로 만들어 리턴

 

다른 방법으로는

 

a = [False,False] + [True*(n-1)]
for i in range(2, int(n**0.5)+1):
    a[i*2::i] = [False]*((n-i)//i)

 

 

 

 

cf) 2,3,5,7 만 쓰면 소수를 구할 수 있다.

출처:

https://this-programmer.tistory.com/409