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

프로그램의 초록색으로 표시한 부분에서 i 값이 n과 같을 때 그 값을 소수로 출력합니다. 실행

결과에서 볼 수 있듯이 나눗셈을 실행한 횟수는 총 78,022 나눗셈을 할 때마다 변수 counter를
증가해 연산 횟수를 계산합니다.
회입니다.
그런데 n이 2 또는 3으로 나누어떨어지지 않으면 2×2인 4 또는 2×3인 6으로도 나누어떨어
지지 않습니다. 그러므로 이 프로그램은 불필요한 나눗셈을 실행하고 있음을 알 수 있습니다.

즉, 정수 n이 소수인지의 여부는 아래 조건을 만족하는지 조사하면 됩니다.

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

예를 들어, 7이 소수인지는 7보다 작은 소수 2, 3, 5로 나눗셈을 실행하면 충분합니다. 이 아
이디어를 적용하여 계산 시간을 줄여 보겠습니다.

알고리즘 개선(1)
앞의 아이디어를 바탕으로 개선한 프로그램이 실습 2-10입니다. 소수를 구하는 과정에서 그

때까지 구한 소수를 배열 prime의 요소로 저장합니다. 이때, n이 소수인지를 판단할 때 쌓아
놓은 소수로 나눗셈을 합니다. 프로그램의 진행에 따라 배열에 저장되는 값이 변화하는 모습
을 그림 2-15에 나타냈습니다. 먼저 2는 소수이므로 점선 안의 그림처럼 값 2를 prime[0]에
저장합니다( 1 ). 배열에 저장한 소수의 개수를 나타내는 변수 ptr은 그림에서 ● 안의 값과 같

습니다. prime[0]에 2를 저장한 바로 다음의 ptr 값은 1입니다.

n ０ ❶ ２ ３ ４ ５ ６
2 － － － － － －
a 3
※ 2로 나누어떨어지지
않습니다. ０ １ ❷ ３ ４ ５ ６
b 5 ※ 2, 3으로 나누어떨어지지 2 3 － － － － －
않습니다. ０ １ ２ ❸ ４ ５ ６
c 7 2 3 5 － － － －
※ 2, 3, 5로 나누어떨어지지
않습니다. ０ １ ２ ３ ❹ ５ ６
d 9 ※ 3으로 나누어떨어집니다. 2 3 5 7 － － －
０ １ ２ ３ ❹ ５ ６
e 11 ※ 2, 3, 5, 7로 나누어떨어지지 2 3 5 7 － － －
않습니다. ０ １ ２ ３ ４ ❺ ６
f 13 2 3 5 7 11 － －

이런 소수들로 나눗셈을 시도합니다.
[그림 2-15] 소수인지 판단하기 위한 나눗셈

3 이상의 소수는 이중 for문으로 구합니다. 바깥쪽 for문은 n의 값을 2씩 증가하여 3, 5, 7, 9,

78 C 알고리즘