037 소수 구하기

첫번째 코드

 

에라토스테네스의 체를 이용해서 소수를 구하는 코드를 작성하자!!

 

먼저 원하는 숫자까지 0으로 구성된 리스트를 만든다!

(소수가 아닌 아이들은 0으로 바꿀 것이다! 이때 0과 1은 모두 0으로 바꾼다!!)

그리고 제곱근까지 반복문을 진행한다!

만약 해당 값이 0이면 다음 숫자를 확인하고

만약에 0이 아니면 i말고 그 다음 i번부터 숫자 끝까지 i의 배수들을 모두 0처리한다.

원하는 부분의 결과만을 추출한다.

 

import sys
import math
input = sys.stdin.readline

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

A = list(range(m+1))
A[1] = 0

for i in range(2, int(math.sqrt(m))+1):
    if A[i] == 0:
        continue
    for j in range(i + i, m+1, i):
        A[j] = 0

for i in A[n:m+1]:
    if i != 0:
        print(i)

 

통과!

생각보다 직관적이어서 응용해서 풀 수 있을 것 같다!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/1929.%E2%80%85%EC%86%8C%EC%88%98%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0

programmers/백준/Silver/1929. 소수 구하기 at main · ornni/programmers