에라토스테네스의 체

import sys
li = sys.stdin.readline

m,n = map(int, li().split())

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

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

arr = sieve(n)
for i in arr:
    if(m <= i):
        print(i)

알고리즘 아이디어

• 2부터 n까지 모든 수를 소수라고 가정 (배열 prime = [True] * (n+1))
• 2부터 시작해서 아직 소수로 남아있는 수(i)의 배수들을 모두 지움(False로 변경)
• 끝까지 반복하면 남아 있는 모두 소수임

시간 복잡도

일반적인 소수 판별 : O(n√n)
에라토스테네스의 채 : O(n log log n)

구현 시 주의점

ii부터 배수를 지우기 시작해야 함 (그보다 작은 배수들은 이미 지워졌음)
-> ii 이전의 배수들은 이미 더 작은 수에서 지워짐 → 중복 연산 필요 없음.

prime[0,1]은 소수가 아니므로 False
결과는 True로 남아있는 인덱스만 출력하면 됨

응용 n~n*2까지 소수 개수

import sys
li = sys.stdin.readline

def sieve(n, n2):
    sieve = [True] * (n2+1)
    sieve[0] = False
    sieve[1] = False
    for i in range(2, int(n2**0.5+1)):
        if sieve[i]:
            for j in range(i*i, n2+1, i):
                sieve[j] = False
    return len([i for i in range(n+1,n2+1) if sieve[i]])
while True:
    
    n = int(li())
    if n == 0:
        break;
    print(sieve(n, n*2))