백준 1929 [파이썬] (에라토스테네스의 체)

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

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

소수는 자신과 1로만 나누어 떨어져야 한다.

해당 수의 제곱근까지만 나누어 보면 알 수 있는데 (num**0.5) 약수가 대칭으로 이루어져있기 때문이다.

24의 약수는 1 2 3 4 6 8 12 24 로 대칭

16의 약수는 1 2 4 8 16

8의 약수는 1 2 4 8 로 대칭

제곱근보다 같거나 작은 수 까지만 나누어 보아도 소수인지 확인이 가능하다는 것이다. (약수의 중간 값까지만 확인.)

즉 24는 1에서 6까지만, 16는 1에서 4까지만, 8은 1에서 2까지만 확인하면 된다.

 

---

에라토스테네스의 체 ?

범위의 모든 소수를 구할 때에는 효율적이지 못하다.

에라토스테네스의 체 알고리즘은

1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2) 2자신을 제외한 2의 배수 지움

3) 3자신을 제외한 3의 배수 지움

4) 4는 지워졌으니 5자신을 제외한 5의 배수 지움

위의 과정을 반복해 지워지지 않은 수들을 소수로 출력.

 

그림의 경우 11**2 > 120이므로 11보다 작은 수의 배수들만 지워도 충분하다.

즉 120보다 작거나 같은 수 가운데 2,3,4,5의 배수를 지우고 남는 수는 모두 소수이다.

 

파이썬으로 구현

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 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
    
    
    #결과
prime_list(20)
[2, 3, 5, 7, 11, 13, 17, 19]