소인수 분해 하기 최적화 알고리즘 혹시 아시나요?
글쓴이: kknd345 / 작성시간: 일, 2005/11/13 - 10:00오후
void soinsu_bunhea( int tmp, DLinked_List* p_List ) { if ( tmp == 0 || tmp == 1) return; while( tmp % 2 == 0 ) { p_List->insert(2,1); tmp /= 2 ; } int sosu = 3; while ( sosu <= tmp ) { if( tmp % sosu == 0 ){ p_List->insert(sosu,1); tmp /= sosu; } else sosu +=2; } }
저의 경우 이런식으로 했는데.. 이것보다 더 최적화 시킬수는 없나요?
Forums:
검색의 생활화를...http://bbs.kldp.org/viewtop
검색의 생활화를...
http://bbs.kldp.org/viewtopic.php?t=39410&highlight=%BC%D2%C0%CE%BC%F6
명예의 전당에 올라간 글이네요-
----
일단, 인수의 후보 상한을 tmp 내지는 tmp/2까지 하는 대신 sqrt(tmp)까지 하면 계산량이 다소 줄어들 겁니다. 나눗셈 테스트를 소수를 가지고만 해볼 수 있다면 계산량이 더 줄어들겠지만, 상당히 큰 수를 다루는 게 아니라면 소수 확인 자체가 도리어 부담이 될 수도 있겠네요;;
상당히 많은 소인수 구하기 알고리즘들이 있나봅니다:
http://en.wikipedia.org/wiki/Prime_factorization
알려진 최고 알고리즘의 시간 복잡도가
라고 하네요...-_-a...
$PWD `date`
소수판단함수 최근 알고리즘.
//=================================================================
// Function ::int PrimeNumner(long iNum)
// return : TRUE - pmenumber corrected.
// FALSE - not primenumner
//-----------------------------------------------------------------
int IsPrimeNumber(long long inNum)
{
ldiv64_t xq;
long long nValue = 4;
long long nDivider = 5; // "5+2=7" for init..
//----------------------sieve method ------------------------------
if (inNum <= 1) return(FALSE);
if ((inNum == 2) || (inNum == 3) || (inNum == 5)) return (TRUE);
if ((inNum%2==0) || (inNum%3==0) || (inNum%5==0)) return (FALSE);
//--------------------- core ----------------------------------------
do{
nValue = 6 - nValue;
nDivider = nDivider + nValue;
xq = ldiv64(inNum, nDivider);
if (xq.rem == 0 ) break;
}while( xq.quot > nDivider );
//------------------- primenumber check -------------------------------------
if (xq.rem ==0) {
/** if (xq.quot == 1) return (TRUE); // idel code **/
if (xq.quot < nDivider) return(TRUE);
return(FALSE);
}else{
return(TRUE);
};
};
일단
소인수 분해 문제는 P문제라는것이 증명되지 않았습니다. 다른말로는 NP문제일 확률이 매우 높다는 것. 소인수분해를 기초로 한 많은 암호화알고리즘도 있고요. 무슨 알고리즘이 제일 잘 최적화되었는지는 모르겠지만 적당히 작은 수에 대해서는 모두 다 비슷할 것이고 많이 큰수에 대해서는 모두다 한없이 오래 걸릴 겁니다. 중간정도 소인수분해는 별로 쓸 일이 없고요. 일단 자신이 분해하고 싶은 수의 크기가 어느정도 되는지 알려주셔야 할듯 합니다.
GMP-ECM
실용적으로는 GMP-ECM이 간편하고 빠릅니다. 데비안 패키지 gmp-ecm으로 있어요.
댓글 달기