내일배움캠프 29일차 - 에라토스테네스의 체

소수란?

소수는 1과 자기자신만을 약수로 가지고있으므로 2부터 n-1 까지 수로 나눠지면 안되는 성질을 가지고있다.

2,3,5,7,11,13,17....

 

1. 기본 방법

모든경우의 수를 검사하는 방법.

O(N)의 시간 복잡도를 가지고있으므로 파라미터값이 커질수록 시간값또한 커지게 된다.

 

	bool isPrime(int num)
	{
		for(int i = 2;i<num;i++)
		{
			if (num % i == 0)
			{
				return false;
			}
		}
		return true;
	}

 

2. 에라토스테네스의 체

에라토스테네스의 체는 가장 대표적인 소수판별 알고리즘 이며 많은 양의 소수를 가장 빠르고 정확하게 구하는 알고리즘이다. 2부터 시작하여 자기자신을 제외한 나머지약수들을 다 지우며 나가며 결과적으로는 소수만 남게된다.

 

	void isPrime(int num)
	{
		int[] temp = new int[num + 1];
		for(int i=2;i<num;i++)
		{
			temp[i] = i;
		}
		for(int i=2;i<=num;i++)
		{
			if (temp[i] == 0) continue;
			for(int j=i+i; j<= num; j+=i)
			{
				temp[j] = 0;
			}
		}
	}