8

我开发了一种算法来查找给定数字的因子。因此，它还有助于确定给定数字是否为素数。我觉得这是寻找因子或素数的最快算法。

该算法确定给定数字是否在 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

请提供您的意见.. 不要犹豫与我联系以获取更多信息。

谢谢，Harish http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

4

3 回答 3

14

“线性时间”是指与输入数据的长度成正比的时间：在这种情况下，您尝试分解的数字中的位数。您的算法不会在线性时间或任何接近它的时间内运行，恐怕它比许多现有的因式分解算法要慢得多。（包括，例如，GNFS。）

于 2011-04-07T12:34:03.287 回答
5

在这种情况下，输入的大小不是n ，而是n中的位数，因此算法的运行时间是输入大小的指数。这被称为伪多项式时间。

于 2011-04-07T12:43:36.837 回答
3

我没有仔细研究过你的算法，但素数测试通常比O(n)快（其中n是输入数）。以这个简单的为例：

def isprime(n):
   for f in range(2,int(sqrt(n))):
      if n % f == 0:
         return "not prime"
   return "prime"

在这里，只需检查直到 sqrt(n) 的所有可能因素，就可以在O(sqrt(n))中确定n是否为素数。

于 2011-04-07T12:42:17.460 回答