알고리즘 ②

두 번째 방법을 살펴보겠습니다. 숫자 6은 소수일까요? 알아보려면 2, 3, 4, 5로 나누어 가다가 그중 하나라도 나누어떨어지면 소수가 아닙니다. 즉, 6 나누기 2를 하면 나머지가 0이어서 소수가 아닙니다. 그러면 3으로는 나누어 보지 않아도 됩니다.

 

숫자 9는 소수일까요? 9 나누기 2를 하면 나머지는 0이 아닙니다. 3으로 나누면 나머지가 0이군요. 계속 나눌 필요 없이 바로 소수가 아니라고 판단할 수 있습니다.

숫자 7은 어떨까요? 2로 나누어 봅니다. 나머지가 0이 아닙니다. 그러면 3으로 나누어 보고, 4로 나누어 보고, 5로 나누어 보고, 6으로 나누어 보아도 나머지는 0이 아니군요. 그러면 소수라고 판단합니다.