[알고리즘/C++] 소수 판별하기

- 소수 : 1과 자기 자신으로만 나누어 떨어지는 수 (ex. 2, 3, 5, 7, 11, ...)
- 소수의 판별
  - 임의의 수 N이 있을 때, 2부터 N-1까지 모두 나누어 나머지가 0인 경우가 있는지 판별하면 된다. 이때 하나라도 거짓인 경우 소수가 아니다.
  - 여기서 계산을 조금 줄인다면, N의 제곱근까지만 연산해도 된다( 그 수를 제곱했을 때 나누어 떨어지면 소수가 아닐테니까 )

#include <iostream>

using namespace std;
int main(void)
{
	bool prime = true;
    int n;
    cin >> n;
    
    for(int i=2 ; i * i <= n; i++)
    {
    
    	if(num % i == 0){
        cout << "소수가 아닙니다";
        return 0;
        }
    }
    
    cout << "소수입니다";
	return 0;
}

- 위에서 1부터 루트 n까지 비교하면 된다고 했지만, 제곱근을 구하는 연산은 많은 자원을 필요하기 때문에, 반대로 제곱이 입력받은 수가 되는가를 비교하여 소수를 판별하게 한다.

---

- 에라토스테네스의 체는 특정 범위의 수가 소수인지 아닌지를 판별하는 방법을 말한다.

출처: 에라토스테네스의 체 - 위키백과

- 일단 0, 1은 고정적으로 소수가 아니고, 2부터 시작해서 2의 배수, 3의 배수를 계속해서 지워나가는 식으로 연산을 하면 된다.

#include <iostream>

using namespace std;

#define MAX 100000
int main(void)
{
	bool arr[MAX] = {1, 1}
    
    for(int i=2;i * i <= MAX;i++}
    {
    	if(arr[i]) continue; //배열 값이 1이면(true - 소수가 아니다) 패스한다.
        
        for( int j = i * i; j < MAX ; j += i ) arr[j] = 1;
    }
	return 0;
}

- 이때 이중 for문 j가 i의 제곱부터 시작하는 이유는, 그 전의 수는 계산 과정에서 이미 소수 여부가 판별이 되었기 때문이다.
- 예를 들어 i=2일 때, 이미 2의 배수는 모두 지워진 상태이다. 즉 i=3이 되었을 때, 3*1은 자명하게 소수인 상태이고, 3*2는 2의 배수 연산 때 이미 소수임이 판별되었으므로 연산할 필요가 없는 상태이다.