C# 소수 구하는 방법들

소수란?

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

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

 

 

1. 기본 방법

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

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

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

 

 

 

2. 제곱근을 이용하는 방법

O(N^(1/2))시간 복잡도를 가진 방법으로 계산의 양이 기본방법보다 줄어든다.

그 이유는 모든 약수들은 대칭을 이루는 성질을 이용하여 제곱근까지만 약수의 여부를 검증하면 

그보다 큰 약수의 수는 검사할 필요가 없어진다

	public bool CalcPrime(int num) 
	{
		int nr = (int)Math.Sqrt(num); 
		for (int i = 2; i <= nr; i++) 
		{
			if (num % i == 0)
				return false; 
		} 
		return true; 
	}

 

 

3. 에라토스테네스의 체

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

	void CalcPrime(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;
			}
		}
	}