소수 판단 함수

C, C++ 전체 링크

 

참고 - 에라토스테네스의 체 - 소수 판단

 

어떤 수가 소수인지 판단하는 방법은 나눠떨어지는 수가 있는지 직접 나눠보면 된다.

 

예를 들어 13을 소수인지 아닌지 판단해보자.

 

1로 나누는 것은 의미가 없으므로, 2부터 나눠보자.

 

13 / 2 는 나눠떨어지지 않는다.

13 / 3 는 나눠떨어지지 않는다.

13 / 4 는 나눠떨어지지 않는다.

 

...

 

13 / 12 는 나눠떨어지지 않는다.

 

따라서 13은 소수이다.

 

하지만 이 과정을 다 해볼 필요는 없다.

2 부터 12까지가 아니라 √13까지만 나눠보면 된다.

 

만약 √13보다 작은 수에서 나눠 떨어지는 수가 있다면 √13보다 큰 수에서도 나눠떨어지기 때문이다.

 

c/c++에서 math 함수를 이용하면 루트를 계산할 수 있지만,

라이브러리를 사용할 수 없는 경우도 있고, 성능을 고려하면 제곱을 이용하는 것이 바람직하다.

#include <stdio.h>

bool isPrime(int n)
{
	if (n == 1) return false; /* 1 예외 처리 */
    
	for (int i = 2; i * i <= n; i++)
		if ((n % i) == 0) return false;

	return true;
}

int main(void)
{
	for (int num = 1; num <= 45; num++)
		if (isPrime(num) == true) printf("%d is prime\n", num);

	return 0;
}

 

1의 경우는 따로 예외 처리를 하도록 해야 한다.