합성수

Composite

수론에서, 합성수란 여러 소수들이 곱해진 수를 의미한다. 다르게 정의하면 약수가 두 개 보다 많은 자연수, 혹은 1과 자기자신을 제외한 다른 약수가 있는 수. 최소의 합성수는 4이다.

어떤 수 [math]\displaystyle{ n }[/math]이 합성수인지의 여부를 확인하는 가장 쉬운 그리고 귀찮은 노가다성 방법은 에라토스테네스의 체를 이용하는 것이다. 그런데 [math]\displaystyle{ n }[/math] 이하의 모든 소수로 나눠볼 필요는 없고, [math]\displaystyle{ \sqrt{n} }[/math] 이하의 소수들만 확인하면 된다. 이유는 소인수분해를 참조하자.