Microsoft MVP성태의 닷넷 이야기
Math: 4. 소수 판정 및 소인수 분해 소스 코드 - C# [링크 복사], [링크+제목 복사],
조회: 31542
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 2개 있습니다.)

소수 판정 및 소인수 분해 소스 코드 - 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;
}




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 2/11/2023]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2016-03-24 11시53분
(BigInteger 급) 소수 판정해주는 웹 페이지
; https://www.wolframalpha.com/input/?i=2&lk=3
정성태

... 121  122  123  124  125  126  127  [128]  129  130  131  132  133  134  135  ...
NoWriterDateCnt.TitleFile(s)
1855정성태2/10/201520723개발 환경 구성: 256. WebDAV Redirector - Sysinternals 폴더 연결 시 "The network path was not found" 오류 해결 방법
1854정성태2/10/201521692Windows: 104. 폴더는 삭제할 수 없지만, 그 하위 폴더/파일은 생성/삭제/변경하는 보안 설정
1853정성태2/6/201551986웹: 29. 여신금융협회 웹 사이트의 "Netscape 6.0은 지원하지 않습니다." 오류 메시지 [5]
1852정성태2/5/201522384.NET Framework: 492. .NET CLR Memory 성능 카운터의 의미파일 다운로드1
1851정성태2/5/201523358VC++: 88. 하룻밤의 꿈 - 인텔 하스웰의 TSX Instruction 지원 [2]
1850정성태2/4/201544164Windows: 103. 작업 관리자에서의 "Commit size"가 가리키는 메모리의 의미 [4]
1849정성태2/4/201524102기타: 51. DropBox의 CPU 100% 현상 [1]파일 다운로드1
1848정성태2/4/201519329.NET Framework: 491. 닷넷 Generic 타입의 메타 데이터 토큰 값 알아내는 방법 [2]
1847정성태2/3/201522677기타: 50. C# - 윈도우에서 dropbox 동기화 폴더 경로 및 종료하는 방법
1846정성태2/2/201531969Windows: 102. 제어판의 프로그램 추가/삭제 항목을 수동으로 실행하고 싶다면? [1]
1845정성태1/26/201532851Windows: 101. 제어판의 "Windows 자격 증명 관리(Manage your credentials)"를 금지시키는 방법
1844정성태1/26/201530795오류 유형: 269. USB 메모리의 용량이 비정상적으로 보여진다면? [7]
1843정성태1/24/201521817VC++: 87. 무시할 수 없는 Visual C++ 런타임 함수 성능
1842정성태1/23/201544315개발 환경 구성: 255. 노트북 키보드에 없는 BREAK 키를 다른 키로 대체하는 방법
1841정성태1/21/201519271오류 유형: 268. Win32 핸들 관련 CLR4 보안 오류 사례
1840정성태1/8/201527514오류 유형: 267. Visual Studio - CodeLens 사용 시 CPU 100% 현상
1839정성태1/5/201520412디버깅 기술: 69. windbg 분석 사례 - cpu 100% 현상 (2)
1838정성태1/4/201540164기타: 49. 윈도우 내레이터(Narrator) 기능 끄는 방법(윈도우에 파란색의 굵은 테두리 선이 나타난다면?) [4]
1837정성태1/4/201526285디버깅 기술: 68. windbg 분석 사례 - 메모리 부족 [1]
1836정성태1/4/201526286디버깅 기술: 67. windbg - 덤프 파일과 handle 정보
1835정성태1/3/201526759개발 환경 구성: 254. SQL 서버 역시 SSL 3.0/TLS 1.0만을 지원하는 듯!
1834정성태1/3/201551408개발 환경 구성: 253. TLS 1.2를 적용한 IIS 웹 사이트 구성
1833정성태1/3/201527461.NET Framework: 490. System.Data.SqlClient는 SSL 3.0/TLS 1.0만 지원하는 듯! [3]
1832정성태1/2/201520535오류 유형: 266. Azure에 응용 프로그램 게시 중 로그인 오류
1831정성태1/1/201528412디버깅 기술: 66. windbg 분석 사례 - cpu 100% 현상 (1) [1]
1830정성태1/1/201527447오류 유형: 265. svchost.exe 프로세스(IP Helper: IPHLPSVC)의 CPU 100% 현상
... 121  122  123  124  125  126  127  [128]  129  130  131  132  133  134  135  ...