[백준 알고리즘] 1929번 소수 구하기

오늘은 백준 알고리즘 사이트에 올라와 있는 1929번 문제를 해결하고 글을 작성하고자 한다.
본 문제는 Python3로 풀이를 진행 하였다.

문제

출처: 백준 알고리즘

문제을 보면 M~N까지의 숫자 중 소수를 구하는 문제임을 충분히 알 수 있다.

풀이

우선 문제에서 보면 알 수 있듯이 소수를 구하는 코드를 작성하면 된다.
소수를 Python코드로 구현 시 다양하게 구현할 수 있지만, 이 문제의 경우 백준 알고리즘에 나와 있는 분류 중 하나인 방법을 사용해보려고 한다.
백준 알고리즘 홈페이지에서는 이 문제에 대한 분류를 다음과 같이 하고 있다.

출처: 백준 알고리즘

따라서 이 문제는 '에라토스테네스의 체'공식을 이용하면 쉽게 풀이할 수 있다.

에라토스테네스란?

- 수학에서 소수를 찾는 방법 중 하나이다.
자세한 설명은 위키백과에 자세히 나와 있기 때문에 링크로 대체한다.

에라토스테네스의 체

에라토스테네스의 체를 이용하여 코드로 구현하면 다음과 같다.

(아래 코드는 로컬 환경에서 테스트를 하기 위해 구현한 코드이다. 따라서 아래 코드를 사용하여 제출했을 경우 시간 초과 및 런타임 에러가 날 수 있다)

def prime_num(m, n):
    primeNumber = [True]*(n+1)
    num = int((n+1)**0.5)

    for i in range(2, num+1):
        if primeNumber[i] == True:
            for j in range(i+i, n+1, i):
                primeNumber[j] = False

    result = [i for i in range(2, n+1) if primeNumber[i] == True]
    return result


def main():
    m, n = map(int, input().split())
    result = prime_num(m, n)

    for i in range(len(result)):
        if result[i] >= m:
            print(result[i])


if __name__ == "__main__":
    main()