728x90
- 소수 : 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의 배수 연산 때 이미 소수임이 판별되었으므로 연산할 필요가 없는 상태이다.
728x90