[파이썬 알고리즘] - 에라토스테네스의 체 (소수 찾기)

🔎 에라토스테네스의 체 이론

• 특정 숫자까지의 모든 소수를 찾아야할 때 효율적인 알고리즘이다.
• 100까지의 숫자 중 소수를 모두 찾을 때
  • 2를 소수로 체크하고, 2의 배수를 모두 지운다.
  • 3을 소수로 체크하고, 3의 배수를 모두 지운다.
  • 4는 2의 배수이기에 지워져 있다.
  • 5를 소수로 체크하고, 5의 배수를 모두 지운다.
  • 6은 2의 배수이기에 지워져 있다.
  • 7을 소수로 체크하고, 7의 배수를 모두 지운다.
  • 8은 2의 배수이기에 지워져 있다.
  • 9는 3의 배수이기에 지워져 있다.
  • 10은 2의 배수이기에 지워져 있다.
  • •••

🔎 에라토스테네스의 체 활용

• 각 테스트케이스별 모든 수를 검사해 소수를 찾지 않고,
  에라토스테네스의 체를 활용해 해당 범위 내 모든 소수를 미리 찾아 표시해 놓았다.
• 각 테스트케이스 별 범위에서 표시한 소수를 찾아 출력함으로써 시간 을 단축했다.
  👉 [백준 4948 파이썬] - 베르트랑 공준

// 에라토스테네스 체 활용 부분 --------------------------------------------------------

N = 123456 * 2 + 1		# 범위 제한
sieve = [True] * N		# 모든 범위 True로 만들어 놓고

for i in range(2, int(N**0.5)+1):	# i는 제곱근만 검사
    if sieve[i]:
        for j in range(2*i, N, i):	# 2의 배수, 3의 배수, •••
            sieve[j] = False		# False로 변경 (소수 X)

// -----------------------------------------------------------------------------

def prime_cnt(n):
    cnt = 0
    for i in range(n+1, n*2+1):
        if sieve[i]:
            cnt += 1
    print(cnt)

while True:
    n = int(input())
    if n == 0:
        break
    prime_cnt(n)

🙏 참고

👉 파이썬으로 소수(prime) 찾기