[python] 백준 - 1929. 소수 구하기

출처: 위키백과

🤔문제 해결

• S2 | 에라토스테네스의 체

소수: 1과 자기 자신 이외의 약수를 가지지 않는 1보다 큰 자연수

숫자 하나하나를 모두 for문을 돌려서 구할 수 있지만 비효율적임. 에라토스테네스의 체를 이용한다.

1. 0부터 구하고자하는 값의 길이 만큼 0의 값을 가진 배열을 만든다. ex) dp = [0, 0, 0, 0, ..., 0]
2. for문으로 2부터 배열의 끝까지 돌면서 자기 자신을 제외한 배수는 전부 1로 바꿔준다. 맨 위의 그림을 보면 이해하기 쉬움
3. 배열에서 0인 녀석들을 print해준다.

💻소스 코드

def eratos(n):
    for j in range(n * 2, E + 1, n):
        dp[j] = 1
    return


S, E = map(int, input().split())
dp = [0] * (E + 1)
dp[0], dp[1] = 1, 1
for i in range(2, E + 1):
    if dp[i] == 0:
        eratos(i)

for i in range(S, E + 1):
    if dp[i] == 0:
        print(i)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기