C++로 두 구간 사이의 소수 찾아 출력하기 – 초보자를 위한 완벽 가이드

소수(素數)란 1보다 큰 자연수 중에서 약수가 1과 자기 자신뿐인 수를 의미합니다. 가장 작은 소수로는 2, 3, 5, 7, 11, 13, 17 등이 있습니다.

두 구간 사이에는 여러 개의 소수가 존재할 수 있습니다. 예를 들어, 5와 20 사이에 있는 소수는 다음과 같습니다.

5, 7, 11, 13, 17, 19

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

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() 함수는 결과를 출력하는 cout 객체와 PrimeNumbers() 함수 호출로 간단하게 구성되어 있습니다. 하한값(lowerbound)과 상한값(upperbound)이 인자로 전달되며, 해당 부분은 다음 코드 조각에서 확인할 수 있습니다.

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

PrimeNumbers() 함수 내부에서는 lbound부터 ubound까지의 각 숫자가 소수인지 여부를 하나씩 검사하고, 소수로 판명되면 즉시 출력합니다. 이 과정은 while 루프를 통해 반복적으로 처리됩니다.

while 루프가 시작될 때 flag 변수의 초기값은 0으로 설정됩니다. 이후 for 루프에서 현재 숫자가 2부터 자기 자신의 절반(lbound/2)까지의 어떤 값으로도 나누어떨어진다면, 즉 약수가 존재한다면 flag 값을 1로 변경하고 break 문으로 반복문을 종료합니다. 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++;
}

추가 최적화 팁

위 코드는 이미 나눗셈 검사 범위를 lbound/2까지만 제한하여 효율성을 높였습니다. 더 나아가 검사 범위를 숫자의 제곱근(sqrt(lbound))까지만 줄이면 불필요한 연산을 크게 줄일 수 있어, 구간이 넓어질 때 실행 속도를 한층 더 향상시킬 수 있습니다.