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

…, 999로 홀수 값만을 생성합니다. 4 이상의 짝수는 2로 나누어떨어지므로 소수가 아니기

때문입니다. 안쪽의 for문은 i 값을 1부터 시작하여 ptr – 1회 반복합니다. 그림에서
안의 값으로 나눗셈하는 것과 같습니다.
변수 i의 증가는 0이 아니라 1부터 시작합니다. 판단 대상인 n이 홀수이므로 prime[0]에 저장된 2로는 나눌 필요가 없
기 때문입니다.

구체적으로 어떤 연산이 수행되는지 다음 네 가지 과정을 예로 들어 살펴보겠습니다.

a 3이 소수인지 판단하는 과정(n은 3)
안쪽 for문은 실행되지 않고 if문에 의해 n 값 3이 prime[1]에 저장됩니다.
ptr의 값은 1입니다. for문의 제어식인 i < ptr(1 < 1)이 성립하지 않으므로 for문의 반복을 수행하지 않습니다. 이어지는
if문은 제어식 ptr == i(1 == 1)이 참이므로 prime[ptr++]에 n을 대입합니다.

실습 2-10 •완성 파일 chap02/prime2.c
01 /* 1,000 이하의 소수를 나열합니다(버전 2). */
실행 결과
02 #include <stdio.h>
03 … 중략 …
나눗셈을 실행한 횟수 :
04 int main(void) 14622
05 {
06 int i, n;
07 int prime[500]; /* 소수를 저장하는 배열 */
08 int ptr = 0; /* 이미 얻은 소수의 개수 */
09 unsigned long counter = 0; /* 나눗셈 횟수 */
10 prime[ptr++] = 2; /* 2는 소수입니다. */ 1
11 for(n = 3; n <= 1000; n += 2) { /* 홀수만을 대상으로 합니다. */
12 for(i = 1; i < ptr; i++) { /* 이미 얻은 소수로 나눕니다. */
13 counter++;
14 if(n % prime[i] == 0) /* 나누어떨어지므로 소수가 아닙니다. */
15 break; /* 더 이상의 반복은 필요 없습니다. */
16 }
17 if(ptr == i) /* 마지막까지 나누어떨어지지 않았다면 */
2
18 prime[ptr++] = n; /* 배열에 저장합니다. */
19 }
20 for(i = 0; i < ptr; i++)
21 printf("%d\n", prime[i]);
22 printf("나눗셈을 실행한 횟수 : %lu\n", counter);
23
24 return 0;
25 }

02• 기본 자료구조 79