[알고리즘] 소수판별

일반적인 소수판별

• 선형탐색을 통해 2 ~ n까지 모두 비교하여 소수를 판별하는 방법
• 시간복잡도는 O(N)이다

#include <iostream>
using namespace std;

// 입력한 n이 소수인지 판별
bool IsPrime(int n)
{
	if (n <= 1)
	{
		return false;
	}

	// n = 2일때 반복문 조건에 맞지 않아 실행x

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

int main()
{
	cout << IsPrime(16);
}

에라토스테네스의 체

• 대량의 숫자들 중 소수를 판별할 때 유용하게 사용되는 방식이다
• 소수들의 배수를 차례차례 삭제해나가면서 마지막에 남은 소수들을 얻어내는 것
• 시간복잡도는 O(N log(log N))으로 N이 커질수록 빠르게 작동한다
  

• 배열내의 소수가 아닌 것들은 0으로 처리하고 소수를 출력할때 0이 아닌것들만 출력되게 함

#include <iostream>
using namespace std;

void Seive(int n)
{
	// 동적배열 생성
	int * array = new int[n + 1];
	
    // 값을 초기화
	for(int i = 0; i <= n; i++)
    {
    	array[i] = i;
    }
    
    // 소수 판별
    for(int i = 2; i <= sqrt(n); i++)
    {
    	for(int j = i * 2; j <= n; j += i)
        {
        	array[j] = 0;
        }
    }
    
    // 소수 출력 (0과 1은 소수가 아니다)
    for(int i = 2; i <= n; i++)
    {
    	if(array[i] != 0)
        {
    		cout << array[i] << " ";
    	}
    }
    
    delete[] array;

}


int main()
{
	Seive(16);
}

바깥쪽 반복을 2부터 제곱근n까지 하는 이유

• 에라토스테네스의 체 방식은 소수의 배수들을 차례차례 제거해나가는 방식인데, 0과 1은 소수에 포함되지 않는다 & 0이나 1부터 시작하게 되면 안쪽 for문에서 j값의 조건이 이상해지고 결과값도 잘못되게 됨
  -> i는 2부터 시작

• n의 배수들 중에서 제곱근n보다 작은 수들의 곱은 n을 넘지 않는다
  -> k * m = n
  -> K 는 제곱근n이하의 값들 / m 은 제곱근n이상의 값들

• ex) n = 36 / k * m = 36
  -> k = 1,2,3,4,6 -> 제곱근 6 이하
  -> m = 6,9,12,18,36 -> 제곱근 6 이상

-> 결국, k x m = n / m x k = n
-> 제곱근 6 이후로는 새로운 배수가 나오지 않는다

출력값 : 2 3 5 7 11 13

안쪽 반복문 j의 값

• 처음 2, 3, 5, 7 ~ 값은 소수
  -> 소수들의 배수를 차례로 제거 해야하기 때문에 시작은 i * 2부터 하여
  소수인 i는 남겨둔다

// 소수 판별
    for(int i = 2; i <= sqrt(n); i++)
    {
    	for(int j = i * 2; j <= n; j += i)
        {
        	array[j] = 0;
        }
    }