[Algorithm/기본지식] 소수 판별하기

 

정수 N이 소수인지 아닌지 판별하는 방법

 

 

정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다.

 

$$a=\sqrt{N}$$​

$$N=b_1\times b_2\times ...b_n\ \left(N의\ 소인수\ 분해\right)$$

​

임의의 정수 N의 제곱근을 a라고 한다.

정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다.

a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다.

​

이를 활용하면

1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우

2. N이 소수가 아닐 때, a보다 크거나 같은 소인수가 있을 경우

3. N이 소수 일 때

​

정수 N을 세 가지 경우로 표현 할 수 있는데, 1번의 경우는 a보다 큰 소인수가 없으므로 N을 2~a(정수 N의 제곱근) 사이의 수로 나누면 N이 소수가 아님을 판별 할 수 있다.

2번의 경우는 임의의 소인수가 a보다 크거나 같으면, a보다 작거나 같은 소인수가 무조건 존재해서 마찬가지로 정수 N을 2~a(정수 N의 제곱근) 사이의 수로 나누면 N이 소수인지 아님을 판별 할 수 있다.

3번의 경우도 마찬가지로 2~a사이의 수로 나누었을때 나뉘지 않으면 소수임을 알 수 있다.