[Math&Algorithm] 소수?

▷소수란?

: 약수가 1과 자기 자신 밖에 없는 수

: 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지지 않는 자연수

소수의 예) 2, 3, 5, 7, 11, 13, 17, 19, 23, ...

 

▷소수를 구하는 방법?

① 자연수 N의 가장 큰 약수는 N/2보다 작거나 같으므로 2부터 N/2까지 나눠보기.

② 자연수 N을 루트 N까지 나눠보기.

    Why? N이 소수가 아니라면 N=a X b 로 표현할 수 있다. (a와 b는 자연수)

            (이 때, a와 b는 a<=b가 성립해야 한다. a > b 라면 두 수를 바꿔서 항상 a <= b로 만들 수 있다.)

            두 수 a와 b가 가장 적은 차이가 나는 경우는 루트 N의 경우이다.

            N=a X b 로 표현했을 때, 이미 N의 소수로 a와 b는 해당되지 않는다.

            따라서 가장 작은 차이로 표현되는 루트N까지 나눠보면 된다.

③ 에라토스테네스의 체 이용한다면 루트 N까지 나눠볼 때 시간을 더 줄일 수도 있다.

: 에라토스테네스의 체는 2부터 N까지 모든 수를 써놓고, 2부터 그 배수를 모두 지우면서 소수를 찾는 방법으로 숫자가 클 때 유용하다.