3

我试图找出任何数字中最大的素数。我正在用python为这个问题编写程序，但我所遵循的算法似乎有问题。它似乎陷入了无限循环。程序是这样的：

def prime(n):
  i=0;
  while(n!=2):
    for i in range(2,n):
        if(n%i==0):
            prime(n/i);
        else:
            continue;
    print("The highest prime factor is: "),n;

print("Enter a number to find its highest prime factor");
n=input();
prime(n);

只需指出这里有什么问题，并提及是否有比这个更好的算法来解决这个问题。

4

7 回答 7

3

编辑：感觉好像没有一些代码我无法弄清楚，所以在这里，你的一些修改：

def prime(n):
  i=2
  while (n%i != 0 and i < n):
    i += 1
  if (i < n):
    return prime (n/i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n)

但是，您的算法效率不高。例如，如果您想要更好的代码并且不需要长时间编码，您可能会考虑使用 Pollard 的 Rho。即使您想坚持自己的想法，也不应该像这样进行可分性测试。您可能想先运行 Erathostene 筛子，以仅测试主要因素的可分性。或者甚至只记住你找到的最后一个除数，以便从那里重新启动算法，而不是从 2 开始。

例如，更好的代码是：

def prime(n,a):
  i = a
  while (n%i != 0 and i*i < n):
    i += 1
  if (i*i < n):
    return prime (n/i, i)
  else:
    print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor")
n=input()
prime(n,2)
于 2013-10-03T11:03:47.147 回答
1

我的解决方案相当简单，并且可以很好地处理在上述大多数解决方案中会导致内存错误的大量数字。

import math

def prime(n):
    for x in range(2, int(math.sqrt(n)) + 1):
        if n % x == 0:
            print n / x
            return prime(n / x)

if __name__ == '__main__':
    prime(898563214300)

最后打印的数字是最大的素数。

于 2014-01-28T16:04:12.737 回答
1

避免递归调用：

def largest_prime_factor(number):
  if number == 1:
    return 1

  test = 2
  while number > 1:
    if number % test == 0:
      number /= test
    else:
      test += 1

  return test
于 2014-01-28T18:58:19.217 回答
0

我可以阻止您的代码陷入循环，如下所示。
陷入循环的主要问题是while(n!=2)（或 1 或其他）是您不更改n.
注意 - 它仍然不会给你素数

def prime(n):
  i=0
  if(n==2):
    print "The highest prime factor is 2"
    return
  for i in range(2,n):
      if(n%i==0):
          prime(n/i)
      else:
          continue
  print("The highest prime factor is: "),n

print("Enter a number to find its highest prime factor");
n=input()
prime(n)

使用 '[python] primes' 搜索 SO 以了解很多正确执行此操作的方法。

于 2013-10-03T11:18:54.167 回答
0

一种没有递归的简单（但效率极低）的方法是：（请原谅我的 python 语法）。

假设 isPrime(k) 是一个函数，如果 k 是素数则返回 true。它可以使用 Erastosenes 筛来实现。

def prime(n):
  i=0;
  largestPrimeFactor = -1;
  for i in range(2,n/2):
     if( isPrime(i) && n%i==0 ) :
         largestPrimeFactor = i;
  print("The highest prime factor is: "),largestPrimeFactor
于 2013-10-03T11:22:04.793 回答
0

考虑一下 C 语言中的这段代码片段，这是一种非常有效的算法，用于查找数字的最大素数。

这些功能是不言自明的。

int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
            return 0;
    return 1;
}

long long int findLargestPrimeFactor(long long int n)
{
    long long int counter=2;
    while(n!=1)
    {
        if(isPrime(n))
            return n;
        while(n%counter==0)
            n/=counter;
        counter++;
   }
   return counter-1;
}
于 2014-09-30T15:26:50.070 回答
0

代码可以进一步优化如下所示，它是用php编写的，但逻辑似乎很公平

for($div=2;$div<=sqrt($n);$div++)
{
    if($n%$div==0)
    {
        $n = $n/$div;
        $div--;
    }
}

通过取平方根，您可以避免不必要的循环。

于 2015-12-16T07:01:15.427 回答