알고리즘 - 소수구하기

알고리즘(수학) - 소수구하기

소수를 구할 때는 두가지 방법이 존재한다.

첫번째는 소수의 정의를 직접 이용해서 구하는 법과 에라토스테네스의 체를 이용하는 방법

1. 소수의 정의를 이용해서 구하는 것은 소수의 정의 즉 "1과 자신으로 나눠지는 수를 이용해서 구하는 것이다."

   코드를 통해 보면

   (가정은 양의 정수만 들어왔다고 가정한다. )

   bool primeCheck(int n) {
       if (n == 1) return false;
       
       for(int i = 0; i<= n; i++) {
           if(n%i == 0)
               return false;
       }
       return true;
   }

   위와 같은 코드를 이용해서 구할 수 있다. 그러나 n을 살펴보면 n이 만약 소수가 아니라면 합성수이고 이 합성수는 두 수의 곱으로 이뤄져있는데 이 각각의 수는 루트(n)보다 하나는 크고 하나는 작기 때문에 나눠지는 수가 존재한다면 하나는 무조건 루트 (n)보다 작게 된다. 즉, 우리는 반복문을 루트(n) 보다 작게 찾으면 된다. 코드를 다시 사용하면

   #include<math.h>
   ​
   bool primeCheck(int n) {
       if (n == 1) return false;
       
       for(int i = 0; i<= sqrt(n); i++) {
           if(n%i == 0)
               return false;
       }
       return true;
   }

   이런식으로 해서 시간 복잡도를 줄일 수 있게 되는 것이다.

2. 두번째 에라토스테네스의 체를 이용하면 되는데 에라토스테네스의 체는 여러개의 소수를 구할때 빠르게 사용할 수 있다.

   

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위처럼 작은 수부터 차례로 확인해서 배수를 전부 지워주면서 소수인지 아닌지 확인을 하게 되는 과정이다. 코드를 통해서 보게되면

// n보다 작은 소수를 모두 구할때
​
bool prime_check[10000]; //인덱스에 해당하는 수가 소수인지 아닌지 check 즉 에라토스테네스의 체
int prime[10000];  //소수를 저장하는 배열 
int prime_cnt = 0; //소수의 개수
int n;
for(int i = 2; i <= n; i++) {
    if(!prime_check[i]) {       //prime_check false이면 소수, true이면 소수가 아니다. 
        prime[prime_cnt++] = i;  // 소수를 prime배열에 넣어주고 
        for(int j = i*2; j<=n; j = j+i) {
            prime_check[j] = true;      //소수의 n배수들은 모두 소수가 아니므로 지워준다. 
        }
    }
}

위와 같은 코드가 나오게 된다.