C++ 언어 소스 코드(소수 찾기 코드) 리팩토링

다음 소스 코드는 http://www.daniweb.com/code/snippet808.html 에서 볼 수 있는 (주어진 범위 안에서) 소수(prime number, 북한 용어로는 씨수) 찾기 C++ 소스 코드이다.
 

1. # include<iostream.h>
2. # include<math.h>
4. void main()
5. {
6.     int flag=0;
7.     unsigned long l, h, temp;
9.     cout<<"Enter the lower limit:"; cin>>l;
10.     cout<<"Enter the higher limit:"; cin>>h;
12.     if(l%2==0)
13.     {
14.          if(l==2) cout<<"2\t";
15.          l++; //taking only odd no
16.     }
18.      for(;l<=h;l+=2, flag=0)
19.      {
20.           temp=sqrt(l);
21.           if(temp%2==0) temp++; //taking only odd no
23.           for(; temp>2; temp--)
24.          {
25.              if(l%temp==0)
26.              {
27.                  flag=1;
28.                  break;
29.               }
30.          }
32.          if(flag==0) cout<<l<<"\t";
33.     }
34. }
    

우선 위의 코드를 파이썬 소스 코드 처럼 들여쓰기 규칙을 엄격히 적용하여 아래 처럼 재작성하였다.

1. #include <iostream.h>
2. # include <math.h>
4. void main() {
6.     int flag = 0;
7.     unsigned long l, h, temp;
9.     cout << "Enter the lower limit: ";
10.     cin >> l;
11.     cout << "Enter the upper limit: ";
12.     cin >> h;
14.     if (l % 2 == 0) {
15.          if (l == 2)
16.              cout << "2\t";
17.          l++;    //  Taking only odd numbers.
18.     }
20.     for (; l <= h; l += 2, flag = 0) {
21.         temp = sqrt(l);
22.         if (temp % 2 == 0)
23.            temp++;    //  Taking only odd numbers.
25.         for (; temp > 2; temp--) {
26.            if (l % temp == 0) {
27.                flag = 1;
28.                break;
29.            }
30.        }
32.        if (flag == 0)
33.            cout << l << "\t";
34.     }
35. }

하지만 아직 표준 C++에 맞지 않으므로 더 고쳐 보았다.

1. #include <iostream>
2. #include <cmath>
4. using namespace std;
6. void main() {
8.     int flag = 0;
9.     unsigned long l, h, temp;
11.     cout << "Enter the lower limit: ";
12.     cin >> l;
13.     cout << "Enter the upper limit: ";
14.     cin >> h;
16.     if (l % 2 == 0) {
17.          if (l == 2)
18.              cout << "2\t";
19.          l++;    //  Taking only odd numbers.
20.     }
22.     for (; l <= h; l += 2, flag = 0) {
23.         temp = sqrt(l);
24.         if (temp % 2 == 0)
25.            temp++;    //  Taking only odd numbers.
27.         for (; temp > 2; temp--) {
28.            if (l % temp == 0) {
29.                flag = 1;
30.                break;
31.            }
32.        }
34.        if (flag == 0)
35.            cout << l << "\t";
36.     }
37. }

이제 컴파일도 잘 되고 실행도 잘 될 것이다.
그러나 중요한 것은 알고리즘이다. 즉 소수인지 아닌지 확인하는 과정이 최적화되어 있느냐의 문제이다. 위의 소소 코드에서 27~32째 줄의 for 반복문 부분을 살펴보자,

            for (; temp > 2; temp--) {
               if (l % temp == 0) {
                   flag = 1;
                   break;
               }
          }

예를 들어 l =  3*1999993 = 5999979 인 경우 sqrt(5999979) ≒ 2449.5 이므로,
for 반복문을 시작하면서 temp = 2995 되고 t = 3 이 될 때 까지 무려 1496번을 반복하게 된다.
이 반복문 안의 나눗셈 과정  l % temp 부분을 l % 3 부터 시작하여 l % 5, l % 7, l % 9 ... 이런 식으로 증가시키면서 반복하는 과정으로 진행한다면, l =  3*1999993 = 5999979 인 경우 ㅣ% 3 = 0 이므로 더 이상 반복하지 않고 바로 반복문을 탈출하고 5999979는 소수가 아니라고 판정내린다.

이런 이유로 인하여, 위 소스 코드를 리팩토링하여 다음 처럼 수정하였다.

1. #include <iostream>
2. #include <cmath>
4. using namespace std;
6. void main() {
8.     int flag = 0;
9.     unsigned long l, h, j, temp;
11.     cout << "Enter the lower limit: ";
12.     cin >> l;
13.     cout << "Enter the upper limit: ";
14.     cin >> h;
16.     if (l % 2 == 0) {
17.          if (l == 2)
18.              cout << "2\t";
19.          l++;    //  Taking only odd numbers.
20.     }
22.     for (; l <= h; l += 2, flag = 0) {
23.         temp = sqrt(l);
24.         if (temp % 2 == 0)
25.            temp++;    //  Taking only odd numbers.
27.         for (j = 3L; j <= temp; j += 2L) {
28.            if (l % j == 0L) {
29.                flag = 1;
30.                break;
31.            }
32.        }
34.        if (flag == 0)
35.            cout << l << "\t";
36.     }
37. }

 
컴파일> cl /GX findPrimes.cpp

실행> findPrimes
Enter the lower limit: 200
Enter the upper limit: 500
211     223     227     229     233     239     241     251     257     263
269     271     277     281     283     293     307     311     313     317
331     337     347     349     353     359     367     373     379     383
389     397     401     409     419     421     431     433     439     443
449     457     461     463     467     479     487     491     499

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.