소수를 구하는 방법

소수를 구하는 방법 3가지를 정리해보고자 한다. 

첫번째는 기본적인 방법이고, 두번째는  첫번째 방법을 약간 변형한것, 세번째는 에라토스테네스의 체를 이용하는 방법이다. 

아무래도 두번째 방법이 시간 복잡도를 고려하지 않는 상황에서는 구현하기 좋기 때문에 상황에 맞게 적절하게 사용하면 될 것 같다. 

 

 

✔️ 소수 

자기 자신보다 작은 두 자연수의 곱으로 나타낼 수 없는 1보다 큰 자연수를 소수 라고 한다. 

쉽게 말해, 1과 자기자신 외에 약수가 존재하지 않는 수 이다. 

 

 

🐙 첫번째 방법 : N 보다 작은 자연수들로 모두 나눠본다 

어떤 임의의 수 N이 소수인지, 아닌지를 구별하는 가장 쉬운 방법은 N 보다 작은 자연수들로 모두 나눠보는것 이다. 

 1< x <N 의 범위를 가지는 x의 값 중에서 나누어떨어지는 수가 있는지 확인하면 된다. 

 

아래의 코드와 같이 반복문을 이용하여 직접 값을 나눠보면서 나머지가 0이 되는지 확인해보면 된다. 

 

🚨 주의할 것은 "num <= 1" 인 경우 대한 처리를 해줘야한다.

왜냐하면 num <=1인 경우, 해당 if문이 없다면  1이하의 수가 들어왔을때 for문이 수행되지 않기 때문에 return true 코드가 실행되어  잘못된 결과가 나오게 된다.  따라서 입력값에 대한 검증이 필요하다는 것에 주의하자. 

public static boolean isPrimeNumber(int num){
        if(num<=1) return false; 
        for(int i=2;i<num;i++){
            if(num%i==0) return false; // 소수가 아님 
        }
        return true; // 소수인 경우 
 }

 

 

이 코드의 경우 데이터의 개수가 N개 일때 시간복잡도가 O(N*N) 이므로,  num의 값이 매우매우 큰 수라면 반복문이 실행되는데 굉장히 오랜 시간이 걸릴 것이다. 

시간 제한이 없다면 상관없겠지만,  일반적인 알고리즘 문제의 경우 시간제한이 존재하기 때문에  이런 코드는 비효율적인 코드 이다. 

 

 

 

🐙 두 번째 방법 : √N 이하의 자연수들로 모두 나눠본다. 

소수가 아닌 수는 1과 자기자신 이외에, 서로 다른 두 자연수의 곱으로 표현된다. 

서로 다른 두 자연수, 즉 약수는 항상 쌍으로 존재한다.

 

따라서  위의 코드처럼 1< x < N의 범위에 있는 모든 자연수를  나눠볼 필요없이, 약수는 쌍으로 존재하기 때문에 둘 중 하나의 값으로 나눠떨어진 것을 확인했다면 굳이 나머지 하나의 값까지 나눠서 확인할 필요가 없다. 

예를들어, 약수의 쌍이 (a,b) 라고 하자. N이 a로 나누어 떨어졌다는건 몫이 b일텐데 굳이 N을 다시 한번 b로 나눠야할 이유가 있을까? 

 

또한,  서로 다른 두 자연수 이기 때문에 하나의 값은 다른 하나의 값보다 항상 작다. 

예를 들어, 약수의 쌍이 (5,5)  처럼 같은 값이 중복해서 존재 할 수 있을까?  12의 약수를 생각해보자 (1,12) (2,6) (3,4) 처럼 하나의 값은 다른 하나의 값보다 무조건 작거나 같다

 

N = a x b 일때, a와 b는 N의 약수이다. (N,a,b는 모두 자연수) 

a ≤ b 라 한다면  a = b 인 경우에 a는 최댓값, b는 최솟값을 가지게 된다. 

 

 a ≤ √N 이며 , a의 최댓값은 √N  이고,  b ≥ √N 이며, b의 최솟값은 √N 이다. 

 

이것을 수학적인 표현을 이용해서 설명해본다면, 약수의 쌍에서 어떤 하나의 값은, 해당 수의 제곱근의 값보다 무조건 작거나 같다  라고 생각해볼 수 있다. 

 

 √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면, N의 약수가 존재한다는 뜻이다. 

따라서 반복문의 범위를  N까지 반복 하는 것이 아닌, √N 이하의 자연수들로 나눠서 소수인지 판별해보자 

 

왜? 약수 중 하나의 값은 반드시 제곱근의 값보다 작거나 같기 때문에, 제곱근의 값보다 작은 범위에서 나눠떨어지는 수가 있다면 제곱근의 값보다 큰 범위에서 나눠떨어지는 수가 반드시 존재한다. 

 

 

 

🪸 제곱근이하의 값만 조사하기 

// 소수인지 판별하는 메서드
    public static boolean isPrimeNumber(int num){
        if(num==1) return false; 
        for(int i=2;i<= Math.sqrt(num);i++){
            if(num%i==0) return false; // 소수가 아님 
        }
        return true; // 소수인 경우 
    }

 

이 메서드를 이용하여 소수를 판별하면, 데이터의 개수가 N개 일때 시간복잡도가 O (N√N ) 이 된다. 

 

 

위의 메서드 처럼 소수인지 판별하기 위해 값을 직접 나눠주는 방식이지만, 범위를 줄여서 더욱 효율적으로 소수인지 판별 할 수 있다. 

하지만, 이 방법의 경우에도 N의 값이 매우매우 커진다면   O (N√N ) 의 시간복잡도로 풀지 못하는 문제가 존재할 것이다. 

 

그래서 필요한것이 바로 에라토스테네스의 체를 이용한 방법이다. 

 

 

 

 

🐙 세번째 방법 - 에라토스테네스의 체 

 

에라토스테네스의 체를 이용하면 일정 범위 안에 있는 모든 소수들을 매우 쉽고, 빠르게 찾아낼 수 있다.

 

소수란 약수가 오로지 1과 자기 자신인 수 이다. 즉, 1과 자기자신을 제외한 수의 배수가 되는 수는 소수가 아니다.
에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘이다.

임의의 수 n 까지  소수를 구하고자 할 때,  2부터 √N 까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.

 

 

이때 왜 제곱근 까지만 값을 확인하는지는 아래의 글을 참고해서 이해하면 된다. 

 

n 이하의 모든 수에 대해서 만족하는 이유는  n보다 작은 자연수 중 가장 큰 수인 n-1만 해도  √n   >  √(n-1)  이다.

 

즉, n보다 작은 수중 소수가 아닌수는 항상  √n 보다 작은 값을 약수로 가지게 되므로,  제곱근의 범위까지만 확인해보면 된다. 

에라토스테네스의 체의 시간복잡도는O(NloglogN) 으로  매우 빠르다고 한다. 왜 그런 시간 복잡도를 가지는지는 아래의 문헌을 참고해서 이해해보면 좋을것 같다.

 

 

 

나무위키- 에라토스테네스의 체 

에라토스테네스의 체

 

반복문의 범위를 제곱근까지만 확인하는 이유에 대해서 정리한 글

에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유

 

에라토스테네스의 체 알고리즘 시간복잡도

Sieve of Eratosthenes - Wikipedia