소수 판정 및 소인수 분해 소스 코드 - C#
*** 유의사항: "프로젝트 오일러 3번 문제"를 풀지 않은 분들의 경우 가능한 풀고 나서 읽기를 바랍니다.
처음에 저는 소인수 분해를 얻기 위해 sqrt(n)까지의 루프를 돌면서 해당 수에 대해 '소수'인지를 판별하는 방법을 사용했습니다. 즉, 나눠져서 0이 나오지 않은 수에 한해서 '소수'인지를 판단하고 그렇다면 '소인수 목록'에 추가하는 것인데요.
이를 위해, 소수를 구하는 방법이 필요했고 다음의 코드가 이를 잘 표현해 주고 있습니다.
// 출처: http://www.dotnetperls.com/prime
public static bool IsPrime(long candidate)
{
if ((candidate & 1) == 0)
{
if (candidate == 2)
{
return true;
}
else
{
return false;
}
}
for (int i = 3; (i * i) <= candidate; i += 2)
{
if ((candidate % i) == 0)
{
return false;
}
}
return candidate != 1;
}
위의 코드에 보면, sqrt(candidate)로 구하지 않고, (i * i)로 판별을 하고 있는데요. 부동 소수점 연산을 필요로 하는 sqrt를 쓰지 않는 것은 괜찮은 아이디어 같습니다. ^^ 그렇긴 해도 사실 차이는 무시할 수 있을 정도인데, 예를 들어 600851475143라는 수에 대해서 테스트를 해보면 다음과 같은 결과를 얻을 수 있었습니다. (물론, JIT 컴파일 시간을 빼기 위해 이미 한번 실행한 코드로 계산된 값입니다.)
i * i: , 600851475143 == Non-Prime, ticks = 11
sqrt: , 600851475143 == Non-Prime, ticks = 15
아마도, i * i는 매 루프마다 수행되는 반면 sqrt로 한번 정해놓으면 재사용이 되기 때문에 성능 향상에 큰 차이는 없는 것 같습니다.
일단, 이렇게 해서 소수 판별 코드는 정했으니 소인수 목록을 구하는 방법은 다음과 같이 처리할 수 있습니다.
static HashSet<long> getFactorizationList1(long number)
{
int rootLoop = (int)Math.Ceiling(Math.Sqrt(number)) + 1;
HashSet<long> primes = new HashSet<long>();
for (int i = 2; i < rootLoop; i++)
{
if ((number % i) != 0)
{
continue;
}
long quotient = number / i;
if (PrimeTool.IsPrime(quotient) == true)
{
primes.Add(quotient);
}
if (PrimeTool.IsPrime(i) == true)
{
primes.Add(i);
}
}
return primes;
}
그런데, 역시 ^^ 머리 좋은 분들이 계시더군요. 아래의 사이트에 보면 더 좋은 알고리즘이 있습니다.
소인수분해 하는 소스 코드 작성해봤는데요.
; http://kldp.org/node/36453
위의 방식으로 갈까 하다가... 혹시나 싶어서 "프로젝트 오일러"의 3번 문제를 풀었던 분들 중에서 코드를 열람해 보니 아이디가 skycolour(소라게) 님의 더 좋은 코드가 있어서 참조해 보았습니다.
static HashSet<long> getFactorizationList2(long number)
{
HashSet<long> primes = new HashSet<long>();
for (long i = 2; i <= number;)
{
if (number % i == 0)
{
primes.Add(i);
number = number / i;
}
else
{
i++;
}
}
return primes;
}
실제로 2개의 알고리즘으로 테스트를 해보면 후자의 방법이 훨씬 더 빠른 속도를 보여주고 있습니다.
Factorization #1, 600851475143 == # of factors: 4, ticks = 36105
Factorization #2, 600851475143 == # of factors: 4, ticks = 218
그런데, 이상하게도 특정 수에 대해서는 2번째 방법의 성능이 더 느리다는 것을 발견했습니다. 바로 해당 수가 소수인 경우입니다.
Factorization #1, 600851475143 == # of factors: 4, ticks = 35101
Factorization #2, 600851475143 == # of factors: 4, ticks = 218
Factorization #1, 100000007 == # of factors: 0, ticks = 283
Factorization #2, 100000007 == # of factors: 1, ticks = 2835450
원인은, 두 번째 방식의 소인수 분해에서 루프의 변수가 n까지 되는 것 때문에 그렇습니다.
static HashSet<long> getFactorizationList2(long number)
{
HashSet<long> primes = new HashSet<long>();
for (long i = 2; i <= number;)
{
if (number % i == 0)
{
primes.Add(i);
number = number / i;
}
else
{
i ++;
}
}
return primes;
}
즉, 주어진 수가 소수인 경우에는 루프를 n이 될 때까지 반복해서 오히려 계산량이 많아지게 되는 것입니다. 아하... 그래서 ^^ 2가지 방식의 장점을 다음과 같이 합쳐 보았습니다.
static HashSet<long> getFactorizationList3(long number)
{
HashSet<long> primes = new HashSet<long>();
long i;
for (i = 2; i * i <= number; )
{
if (number % i == 0)
{
primes.Add(i);
number = number / i;
}
else
{
i++;
}
}
if (primes.Count != 0)
{
primes.Add(number);
}
return primes;
}
그렇게 해서 처리하니, 이번에는 소수와 소수가 아닌 수에 대한 편차가 심하지 않게 개선이 되었습니다.
Factorization #1, 600851475143 == # of factors: 4, ticks = 35598
Factorization #2, 600851475143 == # of factors: 4, ticks = 219
Factorization #3, 600851475143 == # of factors: 4, ticks = 83
Factorization #1, 100000007 == # of factors: 0, ticks = 284
Factorization #2, 100000007 == # of factors: 1, ticks = 2876019
Factorization #3, 100000007 == # of factors: 0, ticks = 360
여세를 몰아서 ^^ 2 ~ n까지의 숫자들에 대해 각각 소인수 목록을 구해오는 방법을 테스트해 보았는데,
for (long i = 2; i < number; i++)
{
getFactorizationList(number);
}
음... 결과가 약간 실망스럽군요. ^^
Factorization Loop #1, 100 == Prime, ticks = 163
Factorization Loop #2, 100 == Prime, ticks = 186
Factorization Loop #3, 100 == Prime, ticks = 133
Factorization Loop #1, 100000 == Prime, ticks = 1503229
Factorization Loop #2, 100000 == Prime, ticks = 219711
Factorization Loop #3, 100000 == Prime, ticks = 196196
Factorization Loop #1, 10000000 == Prime, ticks = 1073849524
Factorization Loop #2, 10000000 == Prime, ticks = 25239246
Factorization Loop #3, 10000000 == Prime, ticks = 25895029
아쉽게도 ^^ 숫자가 커질수록 별다르게 힘을 못 받는 모습을 보여주고 있습니다. (루프마다 계산되는 i * i가 오히려 역효과가 발생한 듯 싶습니다.)
자... 여기서 한번 더 최적화 단계를 들어가는데요. 위와 같이 2 ~ n까지의 숫자들에 대한 소인수 목록을 구해오는 방식에서는 한가지 더 써먹을 것이 있습니다. 바로 중간 중간 '소수' 목록이 자동으로 구해진다는 점인데, 그래서 나누는 수를 단순히 +1씩 증가시킬 것이 아니라 소수 목록에서 발췌를 해오면 되는 것입니다.
따라서, 별도의 소수 목록만을 담은 컨테이너를 유지시켜 주어 다음과 같이 스스로 재활용하는 것이 가능합니다.
static List<long> _primes = new List<long>();
static HashSet<long> getFactorizationList4(long number)
{
HashSet<long> primes = new HashSet<long>();
for (int n = 0; n < _primes.Count;)
{
long prime = _primes[n];
if (prime * prime > number)
{
break;
}
if (number % prime == 0)
{
primes.Add(prime);
number = number / prime;
}
else
{
n++;
}
}
if (primes.Count != 0)
{
primes.Add(number);
}
else
{
_primes.Add(number);
}
return primes;
}
최종적으로, Release 빌드로 설정하여 제 컴퓨터에서 테스트 해보니 다음과 같은 결과를 얻을 수 있었습니다.
Factorization Loop #1, 100 == Prime, ticks = 244
Factorization Loop #2, 100 == Prime, ticks = 194
Factorization Loop #3, 100 == Prime, ticks = 125
Factorization Loop #4, 100 == Prime, ticks = 96
Factorization Loop #1, 100000 == Prime, ticks = 1420842
Factorization Loop #2, 100000 == Prime, ticks = 159405
Factorization Loop #3, 100000 == Prime, ticks = 165762
Factorization Loop #4, 100000 == Prime, ticks = 84306
Factorization Loop #1, 10000000 == Prime, ticks = 882801285
Factorization Loop #2, 10000000 == Prime, ticks = 21123888
Factorization Loop #3, 10000000 == Prime, ticks = 20510663
Factorization Loop #4, 10000000 == Prime, ticks = 11524265
거의 2배 가까운 성능 향상이 있으니, 어느 정도는 만족스러운 결과를 얻은 것 같습니다.
이 외에도
덧글에 보니 재미있는 방법들이 있는데... 음, 그런 것들은 일단 넘어가겠습니다. ^^
첨부된 파일은 위의 코드를 포함한 예제 프로젝트이므로 여러분들도 테스트를 하실 수 있습니다. 더욱 좋은 코드 있으시면 덧글이나, 또는 수학을 많이 모르는 분들도 알기 쉽게 설명해 주시거나 아니면 그냥 아무 생각 없이 가져다 쓸 수 있도록 완성된 코드를 알려주시면 감사하겠습니다. ^^
참고로 아래의 코드는 .NET의 (internal 접근자를 가진) HashHelpers 타입에 구현된 IsPrime 메서드 구현입니다.
public static bool IsPrime(int candidate)
{
if (((uint)candidate & (true ? 1u : 0u)) != 0)
{
int num = (int)Math.Sqrt(candidate);
for (int i = 3; i <= num; i += 2)
{
if (candidate % i == 0)
{
return false;
}
}
return true;
}
return candidate == 2;
}
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]