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 の使用を検討できます。そして、自分の考えに固執したい場合でも、このような分割可能性テストを行うべきではありません. 最初にエラトステネふるいを実行して、素因数による割り切れる可能性のみをテストすることをお勧めします。または、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

再帰を使用しない単純な (しかし非常に非効率的な) アプローチの 1 つとして、次のようなものがあります (私の python 構文を許してください)。

isPrime(k) は、k が素数の場合に true を返す関数であると仮定します。エラストセンのふるいを使用して実装できます。

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

コードは、以下に示すようにさらに最適化できます。php で記述されていますが、ロジックは公平に見えます

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

sq root を取ることで、不必要なループを回避できます。

于 2015-12-16T07:01:15.427 に答える