소수 구하기

소수를 실무에서 구해야 할 경우는 암호화를 할 때 외에는 별로 없습니다. 하지만, 면접 볼 때 소수와 관련된 질문을 받을 때가 있습니다. 참고로, 저는 실무와 별로 관련 없는 이론적인 질문을 하는 그런 면접을 좋지 않게 생각합니다.

소수를 구하려면 소수의 성질을 이용하면 됩니다. 어떤 수 n이 소수인지 판별하려면 다음처럼 하면 됩니다. n을 2부터 n – 1까지 나누어서 나머지가 0일 때가 한 번도 없으면, n은 소수가 됩니다. 그 과정을 구현한 C++ 소스 코드는 아래와 같습니다.

bool is_prime_number(unsigned number)
{
	if (number < 2)
		return false;

	for (unsigned divisor = 2; divisor < number; ++divisor)
		if (number % divisor == 0)
			return false;

	return true;
}

위의 코드를 조금 더 빠르게 바꾼 코드는 아래와 같습니다.

bool is_prime_number(unsigned number)
{
	if (number < 2)
		return false;

	int square_root = static_cast<int>(sqrt(number));
	for (unsigned divisor = 2; divisor <= square_root; ++divisor)
		if (number % divisor == 0)
			return false;

	return true;
}

참고: Cracking the Coding Interview: 150 Programming Questions and Solutions

Advertisements

2 thoughts on “소수 구하기

  1. n-1까지 루프를 도는 것은 좀 낭비이고, (int)(sqrt(n)) 까지만 루프를 돌면 됩니다.
    조금 더 속도를 빠르게 하고 싶은 경우에는
    2의 배수인지 검사한 이후에 3부터 시작해서 (int)(sqrt(n)) 까지 2씩 증가시키면서 찾는 방법이 있습니다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중