[백준/1929] 소수 구하기

출처: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

 소수 판별 알고리즘 중, 에라토스테네스의 체 알고리즘을 이용하면 손쉽게 답을 구할 수 있습니다. 에라토스테네스의 체 알고리즘은 하단 링크에서 설명하고 있습니다.

https://jcy1996.tistory.com/68

소수 판별 알고리즘

 

 소스코드는 다음과 같습니다.

def find_prime_numbers(m, n):
    import math
    
    array = [True for _ in range(n + 1)]
    array[1] = False
    for i in range(2, int(math.sqrt(n + 1)) + 1):
        if array[i]:
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1
    
    for i in range(m, n + 1):
        if array[i]:
            print(i)

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

 에라토스테네스의 체 알고리즘을 이용하여 구간 내 소수를 모두 구하는 함수를 구현했습니다. 따라서 입력을 받은 뒤 함수 인자로 입력을 넣어주면 답을 도출할 수 있습니다.