성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Roll A Lisp In C - Reading ; https...
[정성태] Java - How to use the Foreign Funct...
[정성태] 제가 큰 실수를 했군요. ^^; Delegate를 통한 Bein...
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>소수 판정 및 소인수 분해 소스 코드 - C#</h1> <p> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>*** 유의사항: "<a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=3'>프로젝트 오일러 3번 문제</a>"를 풀지 않은 분들의 경우 가능한 풀고 나서 읽기를 바랍니다.</span> </pre> <br /> 처음에 저는 소인수 분해를 얻기 위해 sqrt(n)까지의 루프를 돌면서 해당 수에 대해 '소수'인지를 판별하는 방법을 사용했습니다. 즉, 나눠져서 0이 나오지 않은 수에 한해서 '소수'인지를 판단하고 그렇다면 '소인수 목록'에 추가하는 것인데요.<br /> <br /> 이를 위해, 소수를 구하는 방법이 필요했고 다음의 코드가 이를 잘 표현해 주고 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > // 출처: <a target='tab' href='http://www.dotnetperls.com/prime'>http://www.dotnetperls.com/prime</a> public static bool IsPrime(long candidate) { if ((candidate & 1) == 0) { if (candidate == 2) { return true; } else { return false; } } for (int i = 3; <span style='color: blue; font-weight: bold'>(i * i) <= candidate</span>; i += 2) { if ((candidate % i) == 0) { return false; } } return candidate != 1; } </pre> <br /> 위의 코드에 보면, sqrt(candidate)로 구하지 않고, (i * i)로 판별을 하고 있는데요. 부동 소수점 연산을 필요로 하는 sqrt를 쓰지 않는 것은 괜찮은 아이디어 같습니다. ^^ 그렇긴 해도 사실 차이는 무시할 수 있을 정도인데, 예를 들어 600851475143라는 수에 대해서 테스트를 해보면 다음과 같은 결과를 얻을 수 있었습니다. (물론, JIT 컴파일 시간을 빼기 위해 이미 한번 실행한 코드로 계산된 값입니다.)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > i * i: , 600851475143 == Non-Prime, ticks = 11 sqrt: , 600851475143 == Non-Prime, ticks = 15 </pre> <br /> 아마도, i * i는 매 루프마다 수행되는 반면 sqrt로 한번 정해놓으면 재사용이 되기 때문에 성능 향상에 큰 차이는 없는 것 같습니다.<br /> <br /> 일단, 이렇게 해서 소수 판별 코드는 정했으니 소인수 목록을 구하는 방법은 다음과 같이 처리할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; <span style='color: blue; font-weight: bold'>if (PrimeTool.IsPrime(quotient) == true)</span> { primes.Add(quotient); } <span style='color: blue; font-weight: bold'>if (PrimeTool.IsPrime(i) == true)</span> { primes.Add(i); } } return primes; } </pre> <br /> 그런데, 역시 ^^ 머리 좋은 분들이 계시더군요. 아래의 사이트에 보면 더 좋은 알고리즘이 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 소인수분해 하는 소스 코드 작성해봤는데요. ; <a target='tab' href='http://kldp.org/node/36453'>http://kldp.org/node/36453</a> </pre> <br /> 위의 방식으로 갈까 하다가... 혹시나 싶어서 "프로젝트 오일러"의 3번 문제를 풀었던 분들 중에서 코드를 열람해 보니 아이디가 skycolour(소라게) 님의 더 좋은 코드가 있어서 참조해 보았습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } </pre> <br /> 실제로 2개의 알고리즘으로 테스트를 해보면 후자의 방법이 훨씬 더 빠른 속도를 보여주고 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Factorization #1, 600851475143 == # of factors: 4, <span style='color: blue; font-weight: bold'>ticks = 36105</span> Factorization #2, 600851475143 == # of factors: 4, <span style='color: blue; font-weight: bold'>ticks = 218</span> </pre> <br /> 그런데, 이상하게도 특정 수에 대해서는 2번째 방법의 성능이 더 느리다는 것을 발견했습니다. 바로 해당 수가 소수인 경우입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Factorization #1, 600851475143 == # of factors: 4, ticks = 35101 Factorization #2, 600851475143 == # of factors: 4, <span style='color: blue; font-weight: bold'>ticks = 218</span> Factorization #1, 100000007 == # of factors: 0, ticks = 283 Factorization #2, 100000007 == # of factors: 1, <span style='color: blue; font-weight: bold'>ticks = 2835450</span> </pre> <br /> 원인은, 두 번째 방식의 소인수 분해에서 루프의 변수가 n까지 되는 것 때문에 그렇습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > static HashSet<long> getFactorizationList2(long number) { HashSet<long> primes = new HashSet<long>(); <span style='color: blue; font-weight: bold'>for (long i = 2; i <= number;)</span> { if (number % i == 0) { primes.Add(i); number = number / i; } else { i ++; } } return primes; } </pre> <br /> 즉, 주어진 수가 소수인 경우에는 루프를 n이 될 때까지 반복해서 오히려 계산량이 많아지게 되는 것입니다. 아하... 그래서 ^^ 2가지 방식의 장점을 다음과 같이 합쳐 보았습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > static HashSet<long> getFactorizationList3(long number) { HashSet<long> primes = new HashSet<long>(); long i; for (i = 2; <span style='color: blue; font-weight: bold'>i * i <= number</span>; ) { if (number % i == 0) { primes.Add(i); number = number / i; } else { i++; } } if (primes.Count != 0) { primes.Add(number); } return primes; } </pre> <br /> 그렇게 해서 처리하니, 이번에는 소수와 소수가 아닌 수에 대한 편차가 심하지 않게 개선이 되었습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Factorization #1, 600851475143 == # of factors: 4, ticks = 35598 Factorization #2, 600851475143 == # of factors: 4, ticks = 219 Factorization #3, 600851475143 == # of factors: 4, <span style='color: blue; font-weight: bold'>ticks = 83</span> Factorization #1, 100000007 == # of factors: 0, ticks = 284 Factorization #2, 100000007 == # of factors: 1, ticks = 2876019 Factorization #3, 100000007 == # of factors: 0, <span style='color: blue; font-weight: bold'>ticks = 360</span> </pre> <br /> 여세를 몰아서 ^^ 2 ~ n까지의 숫자들에 대해 각각 소인수 목록을 구해오는 방법을 테스트해 보았는데,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > for (long i = 2; i < number; i++) { getFactorizationList(number); } </pre> <br /> 음... 결과가 약간 실망스럽군요. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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 <span style='color: blue; font-weight: bold'>Factorization Loop #2, 100000 == Prime, ticks = 219711 Factorization Loop #3, 100000 == Prime, ticks = 196196</span> Factorization Loop #1, 10000000 == Prime, ticks = 1073849524 <span style='color: blue; font-weight: bold'>Factorization Loop #2, 10000000 == Prime, ticks = 25239246 Factorization Loop #3, 10000000 == Prime, ticks = 25895029</span> </pre> <br /> 아쉽게도 ^^ 숫자가 커질수록 별다르게 힘을 못 받는 모습을 보여주고 있습니다. (루프마다 계산되는 i * i가 오히려 역효과가 발생한 듯 싶습니다.)<br /> <br /> 자... 여기서 한번 더 최적화 단계를 들어가는데요. 위와 같이 2 ~ n까지의 숫자들에 대한 소인수 목록을 구해오는 방식에서는 한가지 더 써먹을 것이 있습니다. 바로 중간 중간 '소수' 목록이 자동으로 구해진다는 점인데, 그래서 나누는 수를 단순히 +1씩 증가시킬 것이 아니라 소수 목록에서 발췌를 해오면 되는 것입니다.<br /> <br /> 따라서, 별도의 소수 목록만을 담은 컨테이너를 유지시켜 주어 다음과 같이 스스로 재활용하는 것이 가능합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>static List<long> _primes = new List<long>();</span> static HashSet<long> getFactorizationList4(long number) { HashSet<long> primes = new HashSet<long>(); <span style='color: blue; font-weight: bold'> for (int n = 0; n < _primes.Count;) { long prime = _primes[n]; if (prime * prime > number) { break; }</span> if (number % prime == 0) { primes.Add(prime); number = number / prime; } else { n++; } } if (primes.Count != 0) { primes.Add(number); } <span style='color: blue; font-weight: bold'> else { _primes.Add(number); }</span> return primes; } </pre> <br /> 최종적으로, Release 빌드로 설정하여 제 컴퓨터에서 테스트 해보니 다음과 같은 결과를 얻을 수 있었습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Factorization Loop #1, 100 == Prime, ticks = 244 Factorization Loop #2, 100 == Prime, ticks = 194 Factorization Loop #3, 100 == Prime, ticks = 125 <span style='color: blue; font-weight: bold'>Factorization Loop #4, 100 == Prime, ticks = 96</span> Factorization Loop #1, 100000 == Prime, ticks = 1420842 Factorization Loop #2, 100000 == Prime, ticks = 159405 Factorization Loop #3, 100000 == Prime, ticks = 165762 <span style='color: blue; font-weight: bold'>Factorization Loop #4, 100000 == Prime, ticks = 84306</span> Factorization Loop #1, 10000000 == Prime, ticks = 882801285 Factorization Loop #2, 10000000 == Prime, ticks = 21123888 Factorization Loop #3, 10000000 == Prime, ticks = 20510663 <span style='color: blue; font-weight: bold'>Factorization Loop #4, 10000000 == Prime, ticks = 11524265</span> </pre> <br /> 거의 2배 가까운 성능 향상이 있으니, 어느 정도는 만족스러운 결과를 얻은 것 같습니다.<br /> <br /> 이 외에도 <a target='tab' href='http://kldp.org/node/36453'>덧글</a>에 보니 재미있는 방법들이 있는데... 음, 그런 것들은 일단 넘어가겠습니다. ^^<br /> <br /> <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=704&boardid=331301885'>첨부된 파일은 위의 코드를 포함한 예제 프로젝트</a>이므로 여러분들도 테스트를 하실 수 있습니다. 더욱 좋은 코드 있으시면 덧글이나, 또는 수학을 많이 모르는 분들도 알기 쉽게 설명해 주시거나 아니면 그냥 아무 생각 없이 가져다 쓸 수 있도록 완성된 코드를 알려주시면 감사하겠습니다. ^^<br /> <br /> <hr style='width: 50%' /><br /> <br /> 참고로 아래의 코드는 .NET의 (internal 접근자를 가진) HashHelpers 타입에 구현된 IsPrime 메서드 구현입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } </pre> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
1579
(왼쪽의 숫자를 입력해야 합니다.)