소수 구하기

특정 수가 소수인지 확인하기

기본적으로 2에서부터 입력된 수 미만인 수 중 입력된 수를 나눌 수 있는 수가 존재하면 소수가 아니다.

또한 2와 입력된 값의 사잇값에서 입력값의 루트보다 큰 값은 입력된 값을 나눌 수 없으므로 진행하는 게 의미가 없다.

 

※ 2에서부터 입력값의 루트까지의 수로 입력값을 나눴을 때 나누어 떨어지지 않으면 입력값은 소수다.

 

bool IsPrimeNumber(int number)
{
	// 다음은 for (int i = 2; i <= std::sqrt(number); i++) 과 같다.
	for (int i = 2; i <= number / i; i++)
	{
		if (number % i == 0)
		{
			return false;
		}
	}
	return true;
}

 

특정 범위의 모든 소수 찾기

특정 범위 내의 모든 소수를 찾는 방법으로는 중복 계산을 최소화할 수 있는 에라토스테네스의 체라는 방법을 사용한다. 이는 2에서부터 주어진 범위의 숫자를 순차적으로 나누어 올라가는 것을 반복하여 소수를 찾는 방법이다.

 

※ 수를 한 번씩만 판정하기 때문에 범위가 주어졌을 때 빠르게 소수를 검출할 수 있다.

 

void CalculateAllPrimeNumbers(bool* isPrimeNumberArr)
{
	isPrimeNumberArr[0] = isPrimeNumberArr[1] = false;
	for (int i = 2; i <= 2000000 / i; i++)
	{
		if (isPrimeNumberArr[i])
		{
			for (int j = i * i; j <= 2000000; j += i)
			{
				isPrimeNumberArr[j] = false;
			}
		}
	}
}

 

---

반복문의 시작값이 소수로 판정된 값의 제곱인 이유

 

가령 5에 대한 판정이라고 한다면 다음과 같이 볼 수 있다.

 

5 * 2 = 10

5 * 3 = 15

5 * 4 = 20

5 * 5 = 25

 

이때 5의 제곱이 되기 전 수들은 이미 2, 3, 4(2 * 2)로 처리가 되었기 때문에 처리할 필요가 없음을 알 수 있다.

---