소인수 분해 하기 최적화 알고리즘 혹시 아시나요?

kknd345의 이미지

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;
	}
}

저의 경우 이런식으로 했는데.. 이것보다 더 최적화 시킬수는 없나요?

wariua의 이미지

검색의 생활화를...
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문제일 확률이 매우 높다는 것. 소인수분해를 기초로 한 많은 암호화알고리즘도 있고요. 무슨 알고리즘이 제일 잘 최적화되었는지는 모르겠지만 적당히 작은 수에 대해서는 모두 다 비슷할 것이고 많이 큰수에 대해서는 모두다 한없이 오래 걸릴 겁니다. 중간정도 소인수분해는 별로 쓸 일이 없고요. 일단 자신이 분해하고 싶은 수의 크기가 어느정도 되는지 알려주셔야 할듯 합니다.

feanor의 이미지

실용적으로는 GMP-ECM이 간편하고 빠릅니다. 데비안 패키지 gmp-ecm으로 있어요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.