Page 82 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

05 {
06 int i, n;
07 int prime[500]; /* 소수를 저장하는 배열 */
08 int ptr = 0; /* 이미 얻은 소수의 개수 */
09 unsigned long counter = 0; /* 곱셈과 나눗셈의 실행 횟수 */
10 prime[ptr++] = 2; /* 2는 소수입니다 */
11 prime[ptr++] = 3; /* 3은 소수입니다 */
12 for(n = 5; n <= 1000; n += 2) { /* 홀수만을 대상으로 합니다. */
13 int flag = 0;
counter++
prime[i] * prime[i] <= n
14 for(i = 1; counter ++, prime[i] * prime[i] <= n ; i++) {
15 counter++ ;
counter++
16 if(n % prime[i] == 0) { /* 나누어떨어지면 소수가 아닙니다. */
17 flag = 1;
18 break; /* 더 이상의 반복은 필요 없습니다. */
19 }
20 }
21 if(! flag) /* 마지막까지 나누어떨어지지 않았습니다. */
22 prime[ptr++] = n; /* 배열에 저장합니다. */
23 }
24 for(i = 0; i < ptr; i++)
25 printf("%d\n", prime[i]);
26 printf("곱셈과 나눗셈을 실행한 횟수 : %lu\n", counter);
27
28 return 0;
29 }

곱셈과 나눗셈의 실행 횟수를 나타내는 변수 counter를 증가하는 부분은 회색 박스로 표시한

두 곳입니다. 또한 변수 counter의 값은 아래 두 연산이 실행될 때마다 증가합니다.

곱셈 … prime[i] * prime[i]
나눗셈 … n % prime[i]

이전 버전 2의 계산 횟수(14,622회)와 비교하면 버전 3에서의 계산 횟수는 3,774회로 줄어들
었습니다. 버전 1의 프로그램을 버전 2, 버전 3으로 개선했습니다. 알고리즘에 따라 계산 속
도가 빨라짐을 실감했을 것입니다. 안쪽 for문의 제어식은 쉼표 연산자(comma operator)를 사

용하고 있습니다. 보통 쉼표 식 op1, op2를 평가할 때는 먼저 op1을 평가하고 그 다음에 op2
를 평가합니다. 이 식 전체를 평가하여 얻는 값은 오른쪽 피연산자 op2를 평가하여 얻는 자료

82 C 알고리즘