Python 아리스토테네스의 채 알고리즘

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

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(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 판정 , ex) i가 2라면,(i,n,i) 로 하면 자기자신을 포함한다 (즉 소수인데 sieve[j]=False)로 바뀌어 소수가 아니게 된다.
                                       # 그러므로 i+i 를 만들어 자기자신을 제외한 2+2 2의 배수 부터 시작하는 것이다.
              sieve[j]=False
    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]


print(prime_list(100))

참조 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

움짤을 보면 더 이해가 쉽다

🔑 Key Point

1. 핵심은 정해진 범위 안에서 모든 수를 나열한다.
2. 2의 배수를 지운다. 3의 배수를 지운다.

TIP! 범위를 설정할 때 n의 최대 약수가 sqrt(n)-> 제곱근n 이하이다.

어려웠던 점

for j in range(i+i,n,i)

위 코드에서 왜 range()안의 시작값이 i+i 인지에 대해서 이해 할 수 없었다.
range(i,n,i)로 실제 실행 해보니 [11,13,17~ ] 부터 실행된다. 즉 자기자신이 소수인 부분이
없어진 것이다.

why?

 for i in range(2, m + 1):
        if sieve[i] == True:           
            for j in range(i, n, i): 
              sieve[j]=False

1. 코드를 따라가 보자, m에 10이 들어간다.
2. for i in range(2,11) 2이상 11미만 범위안에서 반복한다.
3. sieve[2] == True : 만약 sieve의 2번째 인덱스가 True 이면,
4. for j in range(2,100,2) 2이상 100미만 2만큼 증가해서 반복한다.
5. 반복하는 코드는 sieve[2]=false 로 바꿔주는것이다.
   즉 소수인 부분이 false 로 바뀐다.

💡 해결점

2를 소수라고 설정하고 알고리즘을 이해하면 쉽게 생각할 수 있다.
당연히 2는 소수인데 어떻게 컴퓨터가 2가 소수인걸 이해할 수 있을까? 라는 생각에서 사로잡혀있었던 것이 어려운점으로 이어진 것이다.
2를 소수로 설정해 2의 배수인 4 6 8 10 을 False로 바꾸고
3을 소수로 설정해 3의 배수인 6 9
5 를 소수로 설정해 5의 배수인 10
을 하면 10 이전에 소수는 2,3,5,7 이 남는다.

👍 코딩할때 직관적으로 이해 할 수 있게 그림이나 순서의 도움도 필요한 것을 느꼈다.