C++ 함수를 활용해 두 구간 사이의 소수 찾기 및 출력하기

소수(Prime Number)란 1보다 큰 자연수 중에서 약수가 1과 자기 자신뿐인 수를 말합니다. 가장 작은 소수들은 2, 3, 5, 7, 11, 13, 17 등입니다.

두 구간 사이에는 여러 개의 소수가 존재할 수 있습니다. 예를 들어, 5와 20 사이에 있는 소수는 5, 7, 11, 13, 17, 19입니다.

이번 글에서는 함수를 사용하여 두 구간 사이의 모든 소수를 찾아 화면에 출력하는 C++ 프로그램을 살펴보겠습니다.

예제 코드

#include <iostream>
using namespace std;
void primeNumbers (int lbound, int ubound) {
    int flag, i;
    while (lbound <= ubound) {
        flag = 0;
        for(i = 2; i <= lbound/2; i++) {
            if(lbound % i == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        cout<<lbound<<" ";
        lbound++;
    }
}
int main() {
    int lowerbound = 20, upperbound = 50;
    cout<<"Prime numbers between "<<lowerbound<<" and "<<upperbound<<" are: ";
    primeNumbers(lowerbound,upperbound);
    return 0;
}

실행 결과

Prime numbers between 20 and 50 are: 23 29 31 37 41 43 47

코드 설명

main() 함수

위 프로그램의 main() 함수는 cout 객체를 이용해 안내 문구를 출력하고, 하한값(lowerbound)과 상한값(upperbound)을 인자로 전달하며 primeNumbers() 함수를 호출하는 역할만 담당합니다. 해당 부분은 아래 코드 조각에서 확인할 수 있습니다.

cout<<"Prime numbers between "<<lowerbound<<" and "<<upperbound<<" are: ";
primeNumbers(lowerbound,upperbound);

primeNumbers() 함수

primeNumbers() 함수에서는 lbound부터 ubound까지의 각 숫자를 하나씩 검사하여 소수인지 여부를 판별하고, 소수라면 화면에 출력합니다. 이 과정은 while 반복문을 통해 처리됩니다.

while 루프 내부에서는 먼저 flag 값을 0으로 초기화합니다. 그다음 for 루프에서 2부터 해당 숫자의 절반까지 나누어 떨어지는지 확인하는데, 만약 나누어 떨어지는 수가 존재하면 그 숫자는 소수가 아니므로 flag를 1로 설정하고 반복문을 종료합니다. for 루프가 끝난 후에도 flag 값이 여전히 0이라면 어떤 수로도 나누어 떨어지지 않았다는 의미이므로, 그 숫자는 소수이며 화면에 출력됩니다. 이 로직은 다음 코드 조각에서 확인할 수 있습니다.

while (lbound <= ubound) {
    flag = 0;
    for(i = 2; i <= lbound/2; i++) {
        if(lbound % i == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
    cout<<lbound<<" ";
    lbound++;
}

마무리

이처럼 플래그(flag) 변수와 반복문을 조합하면 특정 구간 내의 소수를 손쉽게 판별할 수 있습니다. 참고로, 위 코드는 2부터 n/2까지만 검사하므로 효율적이지만, 더 최적화하려면 √n(제곱근)까지만 검사하는 방법을 사용할 수도 있습니다. 이를 통해 불필요한 연산을 줄여 대규모 범위에서도 빠르게 소수를 찾을 수 있습니다.