[백준] 소수 찾기(1978번)

문제 링크

 

풀이

에라토스테네스의 체를 이용하면 탐색 범위를 N에서 N의 루트만큼 줄일 수 있습니다. 자세한 설명은 위키백과로 대신합니다. 위키백과의 설명처럼 120보다 작거나 같은 숫자 중에서 소수를 찾을 때 11 * 11 > 120이기 때문에 11보다 작은 수로 나머지 연산을 수행하면 됩니다. 그 이상의 숫자로 수행하지 않아도 되는 이유는 그들이 앞선 숫자들의 배수이기 때문입니다. i * i <= num에서 등호는 반드시 포함해야 합니다. 소수의 제곱수는 소수로만 나눠지기 때문입니다. 49는 1과 자신을 제외하고도 7로 나눠지므로 소수가 아니지만, 등호를 빼버리면 소수로 판별됩니다.

 

코드

#include <cstdio>

bool IsPrimeNumber(int num)
{
	if (num <= 1)
	{
		return false;
	}

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

	return true;
}

int main()
{
	int N;
	scanf("%d", &N);
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		int num;
		scanf("%d", &num);
		bool result = IsPrimeNumber(num);
		if (true == result)
		{
			++count;
		}
	}
	printf("%d\n", count);
}