以下は、GNU factor のソースの 1 つのバージョンの例です:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
試行分割とポラードのローの両方のルーチンが含まれています。試行分割を使用していくつかの小さな要因 (約 lg(n)^2 まで) を見つけるかのように、クイック スキャンで私に見えます 、この場合は約 4000 です)、残っているものがおそらくプライムでない場合はポラード。この場合は 205432623008947 です 私が 4000 について正しければ、つまり 35129 * 5847949643 .
あなたの例で 2 番目に大きい素因数は 35129 です 、最大の平方根は約 76471 です .約 25,000 の候補を試すだけでよいので、試行分割だけでも高速です。
Gnu coreutils マニュアルには、Pollard の rho アルゴリズムが使用されていることが記載されています。
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html