소수 판별법

[알고리즘] 소수 판별법 소수(prime number) 란? 소수 (Prime Number)는 1과 자기 자신으로만 나누어떨어지는 자연수를 뜻한다. 좀 더 수학적인 표현을 사용한다면 정수 p > 1의 양수인 약수가 1과 p뿐일 때, p를 소수라고 부른다. 가령 자연수 7의 경우 1과 7로만 나누어 떨어지므로 소수이다. 다른 예로 자연수 4의 경우 1, 2, 4로 나누어 떨어지므로 소수가 아니다. 그렇다면 소수에 대해서 알았으니 소수판별법에 대해서 알아보자. 소수판별법 수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다. 추가로, 합성수(合成數, composite number)는 1보다 큰 자연수 중에서 소수가 아닌 수로 합성수의 특징은 약수의 개수가 3개 이상이고 ..