[알고리즘] 소수판별, 에라토스테네스의체

코드보다는 알고리즘 접근 방법에 대해 정리합니다!

keypoint.

자연수는 가운데 약수를 기준으로 각 등식이 대칭적인 형태를 보인다

제곱근이란 어떤 수를 두번 곱하여나오는 수에 대해, 그 수가 나오도록 두번 곱하는 수

소수에 2를 곱할 경우 그 수는 소수가 아니게 된다

 

1. 소수란?

2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지않는 자연수를 말한다.

보통 1부터 N까지의 모든 소수를 출력해야 하는 문제가 나올 수가 있습니다.

 

2. 소수 판별 방법

1) X를 2부터 X-1까지의 모든 수로 나누어 보기

예를 들어, 16이라는 수가 있다면 16을 2로 나누고, 3으로 나누고, 4로 나누고, ... 15까지 나누어 보는 방법입니다.

이때 나머지가 0일 경우에는 소수가 아니게 되어서, 사실 16을 2로 나누었을때 이미 소수가 아님이 증명이 됩니다.

이 방법은 시간 복잡도가 0(X)으로 비효율적인 방법입니다...

 

2) 모든 수를 확인하지 않고 제곱근까지만 확인하기

자연수는 가운데 약수를 기준으로 각 등식이 대칭적인 형태를 보인다는 특징이 있습니다!

16이라는 숫자를 예를 들면,

1 2 4 8 16

이 약수가 되는데, 이를 가운데를 중심으로 양 끝 수를 2개씩 묶어서 곱하면 16이라는 수가 됩니다.

1x16, 2x8, 4x4, 8x2, 16x1

제곱근이란 어떤 수를 두번 곱하여나오는 수에 대해, 그 수가 나오도록 두번 곱하는 수를 말하는데, 16이라는 숫자에서는 4가 제곱근이 되겠지요!

그러므로 소수를 판별할 때에는 4 이상의 수까지 검사하지 않아도 결과는 동일하다는 것을 알게 되었습니다.

 

 

3. 에라토스테네스의 체

에라토스테네스의 체라는 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할때 사용하는 대표적인 알고리즘 입니다.

n=1000이라는 자연수가 주어지고, 1부터 n까지의 모든 소수를 출력하라는 문제가 주어졌을 때, 2번의 2)를 활용해서 1~1000까지의 모든 소수를 구하는 방법을 사용하면 될 테지만... 조금 더 효율적으로 시간을 아낄 수 있는 방법이 있습니다!

이는 소수의 특징을 이용한 것인데, 소수에 2를 곱할 경우 그 수는 소수가 아니게 됩니다. 또한, 그 수에 다시 2를 거듭해서 곱할 경우 그 수들도 소수가 아니게 되는 것이지요.

 

에라토스테네스의 체의 동작원리는 아래와 같습니다.

1) 2부터 N까지의 모든 자연수를 나열한다.
2) 나열한 수 중에서 아직 처리하지 않은 가장 작은 소수 i를 찾는다.
3) 나열한 수 중에서 소수 i의 배수를 모두 제거한다.
4) 더 이상 반복할 수 없을 때까지 2와 3의 과정을 반복한다.

 

이는 알고리즘으로 처리한 값을 재활용 할 수 있다는 점이 특징입니다!