[백준] 1978번 : 소수 찾기 C++

 

 

 

 

백준 온라인 저지 1978번 문제

 

 

소수(prime number)를 찾는 문제이다.

 

 

문제 분석 및 접근 방법

 

주어진 N개의 수 중에 소수가 몇 개 있는지를 출력하는 프로그램이다. 해당 문제는 소수를 판단하는 알고리즘을 짜는 것이 문제이고 알고리즘을 어떻게 짜야지 효율적인지 생각을 한다.

 

먼저 소수의 수학적 정의를 상기하고 수학적 정의를 바탕으로 알고리즘을 작성하고 더 효율적인 방법이 있는지 생각해본다.

 

 

소수의 정의 (Prime number)

 

1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수를 말한다.

 

 

소수를 찾는 방법은 크게 3가지가 있다. 

• 2부터 해당 정수까지 반복문을 통하여 나누어 떨어지는 정수가 존재하는지를 찾는다.
• 2부터 해당 정수의 제곱근까지 반복문을 통하여 나누어 떨어지는 정수가 존재하는지를 찾는다.

 

첫 번째 경우

 

정의대로 for문을 통하여 2부터 자신까지 반복문을 통해 해당 정수를 나누었을 때 나누어 떨어지는 수가 있는지 확인한다. 이런 경우는 해당 정수가 $n$이라고 가정하면 $n$번 반복이 일어나므로 시간 복잡도는 $O$($n$)이다.

bool isPrimeNumber(int checknum)
{
	if (checknum == 1)
		return false;
	int i;
	for(i = 2; i <= checksum; ++i)
	{
		if (checknum % i == 0)
		{
			return false;
		}
	}
	return true;
}

 

두 번째 경우

 

두 번째 경우는 약수의 특성을 이용하는 방법이다. 어떤 정수의 약수는 제곱근을 기준으로 대칭을 이루게 된다. 예를 들면 12의 약수는 1, 2, 3, 4, 6, 12이다. 1 * 12, 2 * 6, 3 * 6으로 제곱근을 기준으로 좌우측 약수들이 대칭으로 곱해져야 정수가 된다. 또한, 소수는 2 이상 해당 정수 이하에 약수가 하나라도 존재하면 안 되기 때문에 반복문의 범위를 제곱 근수까지 줄여서 알고리즘의 효율을 높일 수 있다. 시간 복잡도는 $O$($n^½$)가 된다.

bool isPrimeNumber(int checknum)
{
	int root = (int)sqrt(checknum);
	if (checknum == 1)
		return false;
	int i;
	for(i = 2; i <= root; ++i)
	{
		if (checknum % i == 0)
		{
			return false;
		}
	}
	return true;
}

 

* sqrt()

해당 함수는 ctime 헤더에 존대하는 함수이다. 

함수원형은 double sqrt(double)이다. 따라서 반환되는 값이 double형이기 때문에 integer형 변수 root에 type casting(형 변환)을 해주었다. 또한 integer형 매개변수 checknum은 sqrt함수에 전달될 시 자동으로 type casting이 된다. 

 

 

소수를 구하는 방법에는 에라토스테네스의 체라는 방법이 존재한다. 해당 방법은 백준 1929번 : 소수 구하기 문제에서 다루도록 한다.