我已经开发了一个算法来查找给定数字的因数。这也有助于查找给定数字是否为质数。我认为这是查找因数或质数的最快算法。
该算法在5*N(其中N是输入数字)的时间范围内判断一个数字是否为质数。因此,我希望将其称为线性时间算法。
如何验证这是可用的最快算法?有人能帮忙吗?(比GNFS和其他已知算法更快)
以下是算法:
请提供您的评论...如需更多信息,请随时与我联系。
谢谢, 哈里什 http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html
该算法在5*N(其中N是输入数字)的时间范围内判断一个数字是否为质数。因此,我希望将其称为线性时间算法。
如何验证这是可用的最快算法?有人能帮忙吗?(比GNFS和其他已知算法更快)
以下是算法:
Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.
Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
r = 0; //answer is found
End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
mL = mL-1;
r = r+ mR;
temp1 = r/mL;
mR = mR + temp1;
r = r%mL;
}
End; //mR and mL has answer
请提供您的评论...如需更多信息,请随时与我联系。
谢谢, 哈里什 http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html