1.素數表,從小到大去試除,一直到當前質數的平方大於試除後剩下的數.

這樣最佳化後的效率會比較高,至少在long int範圍內.

正好剛寫的:

for (kindp = 0, i = 0; prime[i] * prime[i]

if (y % prime[i] == 0)

{ pp[kindp] = prime[i];

ep[kindp] = 0;/*當前質因數的次數*/

while (y % prime[i] == 0)

{

y /= prime[i];

ep[kindp]++;

}

kindp++;

}

if (y != 1)/*處理最大的一個質數*/

{

kindp++;

ep[kindp]=1;

pp[kindp]=y;

}

下面的是更先進一點的方法,但是要求不高的時候用第一種比較好.

2.Pollard"s rho method

3.Pollard"s p - 1 method

4.Lenstra"s elliptic curve factorization method

5.The quadratic sieve factorization method