소수! 소수가 뭘까?
소수는 1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수를 말한다.
예를들면 2, 3, 5, 7, 11, 13과 같은 숫자들이 소수다!
만약 어떤 양의정수 N을 입력받았을때, N이 소수인지 아닌지 판별하는 로직을 구현하라는 미션을 받았을때 어떤식으로 구현해야할까??
가장 먼저 드는 생각은 입력받은 N이라는 숫자를 2부터 N-1까지 차례대로 나누기 연산을 통해서 나누어 떨어지는 숫자가 있다면 소수가 아니고, 나누어 떨어지는 숫자가 없다면 소수가 되겠다.
왜 1부터 시작하지 않고 2부터 시작하냐?
그건 바로 1은 모든 숫자의 약수이기 때문이다~
위의 아이디어를 코드로 옮겨보면 아래처럼 소수를 판별하는 함수를 작성할 수 있을거다!
int is_prime_number(int n) {
for(int i = 2; i < n-1; i++) {
if(!(n % i)) {
return false;
}
}
return true;
}C언어에서 boolean값인 true / false를 사용하기 위해서는 stdbool.h를 include해서 사용해야 한다.
별다른 어려움은 없이 구현할 수 있는데, 문제가 있다.
바로 소수인지 아닌지 판별하는데 오래걸릴 여지가 있다는 것이다.
소수인지 아닌지 판별하는 방법 자체가 개선이 필요하다는것은 아니고, 나눗셈연산을 하는 범위를 N-1에서 더 좁힐수는 없는지 생각해볼 여지는 있다.
예를들어서 823이라는 숫자가 소수인지 아닌지 판별해야한다고 가정하자, 그러면 2부터 822 즉 821번의 나눗셈 연산을 통해서야 비로소 823이라는 숫자가 소수라는걸 알 수 있다.
그럼 어떤식으로 개선을 하면 좋을까??
먼저 13이라는 숫자를 예시로 들어보면, 위의 로직대로라면 13이라는 숫자가 소수인지 아닌지를 판별하기 이해서는 2부터 12까지 모두 나눠봐야 하는데, 그럴필요가 있을까!!?
잘 생각해보면 2부터 13의 제곱근 까지의 정수로만 나눠봐도 알 수 있지 않을까??
12라는 숫자를 예시로 들어보면, 12는 2x6, 3x4, 4x3, 6x2의 조합이라는걸 알 수 있다. (오호~?)
그리고 앞쪽의 두 조합과, 뒤쪽의 두 조합이 서로 대칭이 되는 모양이라는걸 눈치챌수 있다!
따라서 13이라는 숫자가 소수인지를 판별하려면 13의 제곱근 까지만 나누어 보면 된다라는걸 알수있다!
int is_prime_number(int n) {
for(int i = 2; i <= (int)sqrt(n); i++) {
if(!(n % i)) {
return false;
}
}
return true;
}N-1 까지가 아닌, N의 제곱근 까지만 for loop를 순회하기 때문에 얼핏 생각하기에는 거의 수행시간이 파격적으로 빨라질것 같지만 항상 그렇지만도 않다.
왜나하면 sqrt 함수는 실수형의 데이터를 인자로 받아서 실수형의 데이터를 반환하는 함수다.
그래서 형변환 연산자를 통해서 캐스팅을 해주는 것이다.
여튼저튼, 컴퓨터한테 실수형의 숫자도 정수형처럼 빠르게 연산해달라고 하는건 무리이기 때문에 이 부분이 약점이다.
다만.
2 ~ N-1 까지 순회하는 경우에는 숫자가 커질수록 수행시간이 엄청 커지게 된다.
예를 들어서 7919같이 엄청큰 소수를 입력으로 받으면 7917번의 루프를 돌아야만 판단이 가능하지만,
제곱근을 사용하는 경우에는 N이 크거나 작아도 평균적인 시간복잡도를 보여주기때문에 입력 자료형에 크게 영향을 받지 않고 고른 성능을 나타내 준다는게 큰 장점이다.
