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

b 5가 소수인지 판단하는 과정

prime[1]에 저장한 3으로 나눗셈을 실행합니다. 3으로 나누어떨어지지 않기 때문에 n의 값
5를 prime[2]에 저장합니다.
모든 의 값으로 나누어떨어지지 않고 안쪽 for문이 끝까지 실행되면 for문 종료 시 i의 값은 ptr과 일치합니다. 즉,
i와 ptr의 값이 같으면 소수입니다( 2 ).

c 7이 소수인지 판단하는 과정

prime[1]에 저장한 3과 prime[2]에 저장한 5로 나눗셈을 실행합니다. 소수라고 판단되므로
n의 값 7을 prime[3]에 저장합니다.

d 9가 소수인지 판단하는 과정

prime[1]에 저장한 3으로 나눗셈을 실행합니다. 3으로 나누어떨어지므로 소수가 아닌 합성
수라고 판단합니다.
의 값으로 나누어떨어져 안쪽의 for문이 중단되면 for문 종료 시 i의 값은 ptr보다 작습니다. 즉, i의 값이 ptr보다
작으면 합성수입니다.

이렇게 알고리즘을 수정하면 나눗셈을 수행하는 횟수가 78,022회에서 14,622회로 감소합

니다. 두 프로그램을 비교하면 다음과 같은 결론을 내릴 수 있습니다.

1. 같은 답을 얻는 알고리즘은 하나가 아니다.
2. 빠른 알고리즘은 메모리를 많이 요구한다.

알고리즘 개선(2)
100의 약수를 그림으로 나타내면 아래의 그림 2-16과 같습니다(단, 1 × 100은 제외합니다).

50

① 2×50
40
② 4×25
이 범위의 나눗셈만
③ 5×20
30 수행하면 됩니다.
대칭 ④ 10×10
⑤ 20× 5
20
⑥ 25× 4
⑦ 50× 2
10

0
0 10 20 30 40 50
[그림 2-16] 100의 약수의 대칭성

80 C 알고리즘