Python으로 구간 내 모든 소수를 출력하는 프로그램 만들기

이 글에서는 주어진 구간 안에 있는 모든 소수(Prime Number)를 찾아 출력하는 Python 프로그램을 다뤄보겠습니다.

문제 정의

시작 값과 끝 값으로 이루어진 하나의 구간이 주어졌을 때, 해당 범위에 포함된 모든 소수를 계산하여 출력해야 합니다.

접근 방법: 브루트 포스(Brute Force)

여기서는 가장 기본적인 방법인 브루트 포스 방식을 사용합니다. 소수의 정의에 따르면, 소수란 1과 자기 자신만을 약수로 가지는 수입니다. 즉, 2부터 자기 자신보다 작은 수 중 하나라도 나누어 떨어지면 소수가 아닙니다.

따라서 각 숫자마다 소수 조건을 검사하고, 조건이 참일 때마다 해당 숫자를 출력하면 됩니다.

구현 예제

start = 1
end = 37
for val in range(start, end + 1):
    # val이 2와 val 사이의 어떤 수로도 나누어지지 않으면 소수
    if val > 1:
        for n in range(2, val):
            if (val % n) == 0:
                break
        else:
            print(val)

실행 결과

2
3
5
7
11
13
17
19
23
29
31
37

코드 설명

코드의 동작 흐름은 다음과 같습니다.

1. start와 end 변수로 검사할 구간을 지정합니다.
2. range(start, end + 1)을 통해 구간의 모든 숫자를 하나씩 확인합니다.
3. 1은 소수가 아니므로 val > 1 조건으로 제외합니다.
4. 내부 반복문에서 2부터 val - 1까지의 수로 나누어 떨어지는지 검사합니다.
5. 나누어 떨어지는 수가 있으면 break로 반복문을 종료하고, 끝까지 살아남은 수만 else 블록에서 출력됩니다.

모든 변수는 지역 스코프(local scope) 내에서 선언되며, 위 실행 결과에서 그 참조 값을 확인할 수 있습니다.

마치며

이번 글에서는 소수의 기본적인 정의를 활용한 브루트 포스 방식으로 주어진 구간 내의 모든 소수를 출력하는 방법을 알아보았습니다. 이 방법은 이해하기 쉽지만 숫자가 커질수록 연산량이 늘어나므로, 더 큰 범위를 다룰 때는 에라토스테네스의 체와 같은 효율적인 알고리즘을 사용하는 것이 좋습니다.