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

n의 값을 2부터 시작하여 1,000이 될 때까지 1씩 증가하면서 그 값이 소수인지를 판단합니

다. 판단하는 과정을 그림 2-14와 같이 정리했습니다. 그림 2-14를 통해 9와 13을 예로 들어
구체적으로 살펴보겠습니다.

9일 때 소수인지 판단하는 방법

안쪽의 for문에서 i 값을 2, 3, …, 8로 증가합니다. 9는 i가 3일 때 나누어떨어지므로 break문
이 동작하여 for문의 반복이 중단됩니다. 따라서 나눗셈은 ‘2, 3’ 2회만 진행됩니다. for문을
벗어날 때의 i 값은 3입니다.

13일 때 소수인지 판단하는 방법
안쪽의 for문에서 i 값을 2, 3, …, 12로 증가합니다. 13은 한 번도 나누어떨어지지 않습니다.
따라서 11회의 나눗셈이 모두 수행됩니다. for문을 벗어날 때의 i 값은 13입니다.

검은색이고 두꺼운 글자 3 나눗셈을 실행, 나누어떨어지지 않음
소수
초록색이고 기울어진 글자 3 나눗셈을 실행, 나누어떨어짐
합성수 검은색이고 가는 글자 3 나눗셈이 필요하지 않음

n 나누는 수 나눗셈 횟수
2
3 2 1
4 2 3 1
5 2 3 4 3
6 2 3 4 5 1
7 2 3 4 5 6 5
8 2 3 4 5 6 7 1
9 2 3 4 5 6 7 8 2
10 2 3 4 5 6 7 8 9 1
11 2 3 4 5 6 7 8 9 10 9
12 2 3 4 5 6 7 8 9 10 11 1
13 2 3 4 5 6 7 8 9 10 11 12 11
14 2 3 4 5 6 7 8 9 10 11 12 13 1
15 2 3 4 5 6 7 8 9 10 11 12 13 14 2
16 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

[그림 2-14] 소수인지 판단하기 위한 나눗셈

안쪽 for문의 반복이 종료된 시점에서 변수 i의 값은 아래와 같습니다.

•n이 소수인 경우 : n과 같은 값 (for문이 끝까지 실행됨)
•n이 합성수인 경우 : n보다 작은 값 (for문이 중단됨)

02• 기본 자료구조 77