소수 판별

소수(Prime Number) : 1과 자기 자신으로만 나누어 떨어지는 수.

 

암호 분야에서 기술적으로 이용하고 있는 중요한 수.

 

임의의 수 N의 소수 구하기.

 

첫번째 방법 

2~N-1까지 모든 수로 나누어 보면서 나머지가 0인 경우가 있는지 판단하는 방법.

0인 경우가 한번이라도 있으면 소수가 아님.

 

두번째 방법.

2~ N의 제곱근 까지 모든 수로 나누어보고 나머지가 0인 경우가 없으면 그보다 큰 수는 당연히 없다.

하지만 컴퓨터 입장에서는 제곱근 연산이 부담되므로 첫번째 방법이 나음.

 

세번째 방법.

에라토스테네스의 체 : 여러개의 수에 대해 소수 판별을 해야할 때 사용할 수 있다.

1. 1을 제외한 모든 수를 표에 적는다.

2. 현재 수가 지워져 있다면 다음 수로 이동.

3. 현재 수가 지워져 있지 않다면, 현재 수를 제외한 모든 배수를 지우고, 2로 돌아간다.

 

이를 반복하면 남은 수 모두가 소수.