[알고리즘 #3] 소수 판별 알고리즘

** 반응형 광고 **

1. 소수 (prime number) 란?

1과 자기 자신만을 약수로 가지는 수로 1보다 큰 수 (2, 3, 5, 7, 11, 13 ..)

2. 소수 판별법

1) 나머지가 0인 수 검사

어떤 수 A가 소수인지 판별하기 위해서는 A를 2부터 A보다 1작은 수까지 나누어서 나머지가 0인 경우가 있는지 검사함.

MOD(A, 2) ~ MOD(A, A-1) = 0 인 경우를 check

2) 제곱근 이용 

어떤 수 A의 제곱근까지의 수 중 한 개의 수에 대해서라도 나누어 떨어지면 소수가 아님.

MOD(A, 2) ~ MOD(A, SQRT(A)) = 0 인 경우를 check

당연히, 1) 의 방식보다 성능이 좋다.

3. 에라토스테네스의 체

1~N 까지의 수 중에서 소수를 구하고자 한다면 에라토스테네스의 체를 활용하는 것이 좋다. 모든 자연수는 소수들의 곱으로 표현되기 때문에 2의 배수, 3의 배수, 5의 배수와 같이 N까지의 수 중 소수의 배수를 체로 걸러내는 방식이다. 다음 그림을 보고 1~ 120 사이의 소수를 파악하는 알고리즘을 이해해보자. (소스 코딩을 할 때 Array[120] 을 활용해서 짜보자)

** 큰사각형 광고 **