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

연습 Q10 배열 a의 모든 요소의 순서를 뒤섞는 shuffle 함수를 작성하세요(n은 요소 개수입니다).
문제
void shuffle(int a[], int n);

소수의 나열

어떤 정수 이하의 소수를 모두 나열하는 알고리즘을 살펴보겠습니다. 소수는 자신과 1 이외
의 정수로 나누어떨어지지 않는 정수입니다. 예를 들어 소수인 13은 2, 3, …, 12 가운데 어떤
정수로도 나누어떨어지지 않습니다. 그러므로 어떤 정수 n에 대하여 아래의 조건을 만족하면

소수임을 알 수 있습니다.

2부터 n - 1까지의 어떤 정수로도 나누어떨어지지 않습니다.

만약 나누어떨어지는 정수가 하나 이상 존재하면 그 수는 합성수(composite number)입니다.

다음은 1,000 이하의 소수를 나열하는 프로그램입니다.
이 프로그램은 아직 배열을 사용하지 않습니다. 배열은 개선된 버전 2, 버전 3의 프로그램에서 사용합니다.

실습 2-9 •완성 파일 chap02/prime1.c
01 /* 1,000 이하의 소수를 나열합니다(버전 1). */
실행 결과
02 #include <stdio.h> 2
03
3
04 int main(void) 5
05 { 7
06 int i, n; … 중략 …
07 unsigned long counter = 0; /* 나눗셈 횟수 */ 991
08 for(n = 2; n <= 1000; n++) { 997
09 for(i = 2; i < n; i++) { 나눗셈을 실행한 횟수 : 78022
10 counter++;
11 if(n % i == 0) /* 나누어떨어지면 소수가 아닙니다. */
12 break; /* 더 이상의 반복은 불필요합니다. */
13 }
14 if(n == i) /* 마지막까지 나누어떨어지지 않았습니다. */
15 printf("%d\n", n);
16 }
17 printf("나눗셈을 실행한 횟수 : %lu\n", counter);
18
19 return 0;
20 }

76 C 알고리즘