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

문제요약 (1929. 소수 구하기 )

M 이상 N 이하의 소수를 모두 구해 출력한다.

소수를 구하는 여러가지 방법 중 에라토스테네스의 체를 이용해 구해보자

1929번: 소수 구하기

 

풀이를 위한 부연 설명

• 에라토스테네스의 체의 원리
  1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성
  2. 2부터 숫자를 시작해 숫자가 지워지지 않은 경우 현재 선택된 숫자의 배수에 해당하는 수를 탐색하며 지운다.
     단, 처음 선택된 수는 지우지 않는다.
  3. 리스트를 반복한다.
• n = a * b ( a > b) 라는 것은 n = b * a와 같다.
  • 즉 n의 제곱근까지만 탐색하면 ( = 절반만 탐색 ) 모든 수를 탐색한다.
• 소수판별에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

 

[코테 알고리즘] 소수 판별&투 포인터 / 관련 문제

 

코드 

import sys
input = sys.stdin.readline

from math import sqrt

start, end = map(int, input().split())

num = [i for i in range(end + 1)]

num[0] = 0
num[1] = 0

for i in range(2, int(sqrt(end)) + 1):
    if num[i] == 0:
        continue
    for j in range(i + i, end + 1, i):
        num[j] = 0

for i in range(start, end + 1):
    if num[i] != 0:
        print(num[i])

 

 

기억할 점

• 에라토스테네스의 체는 코딩테스트에서 소수를 판단할 때 자주 쓰인다.