1

私に述べられた問題はこれでした：

「数 600851475143 の最大の素因数は?」

このプログラムは、答えを見つけるために使用されます。C を使用すると、まさにこれでした。

#include<math.h> // for remainder because % does not work with double or floats
#include<stdio.h>  
main()
{
    double x=600851475143,y=3.0;
    while(x!=y)                         // divide until only the number can divide itself
    {
        if(remainder((x/y),1)==0.0)     // if x is divisible by y which means it is a factor then do the magic
        {
            x=x/y;                      // divide the number x by y thereby reducing one constituent factor
        }
        y=y+2;                          // add 2 simply because only odd numbers can be prime and hence only prime numbers can be prime factors
    }
    printf("%lf",y);                    // do the printing magic
}

質問は、x をチェックしてすべての奇数で除算しようとすることですが、すべての奇数が素数ではないことに注意してください。アルゴリズムのこの欠陥により、実際には私は素因数のチェック (奇数因数ではない)。

驚くべきことに、このプログラムが吐き出す答えは正しいので、答えを確認しました。

どうすればこれを回避できますか？それは意味がありません。

4

4 に答える 4

4

アルゴリズムには 3 つの欠陥があることに注意してください。

  1. 2も素数です
  2. 素数でも奇数でもない数（9 など）を割ることがあります。
  3. 素数を 2 回以上分割することはありません (27 などの数に対して予想されるように)。

これらから、次の 2 つの条件が当てはまる場合、壊れたアルゴリズムは正しい答えをもたらすと結論付けることができます。

  1. 入力番号が奇数です (したがって、2 のスキップは問題になりません)
  2. 数n = p1*p2*...*p_kをp_iすべて素数とする。それぞれについてj!=i: p_i != p_j. ここでは、実際には各素数が入力数の因数になるのは 1 回のみであることを意味するため、問題 2+3 は「回避」されます。(問題 2 - 回避される理由は些細なことです。問題 3 は、関連するすべての素因数で既に数を除算しているため、回避されます。つまりm=p_i1*...*p_ic、数値はすべての素因数で既に除算されているため、それぞれについて、次のp_i1,...p_icように除算することに失敗します。m.
于 2013-05-14T08:13:25.260 に答える
3

他の誰もがあなたのプログラムの何が問題なのかをあなたに言っているので、試行除算を使用して整数を素因数分解するための正しいアルゴリズムを示します。

function factors(n)
    f, fs := 2, []
    while f * f <= n
        if n % f == 0
            append f to fs
            n := n / f
        else f := f + 1
    append n to fs
    return fs

これにより、コードに関する 2 つの問題が解決されます。まず、2 の因数を適切に識別します。次に、すべての因数をその多重度とともに返します。

非素数による除算に関する質問に答えるには、これはパフォーマンスの問題であり、正確性の問題ではありません。試用除数は昇順でテストされるため、複合除数は、それらの構成素数がテストされたときに、因数分解される数から既に削除されています。つまり、コンポジットによる除算は役に立ちませんが、結果には影響しません。

もちろん、整数を扱うときは浮動小数点演算を使用しないでください。C では、long long integer を超えると、おそらくgmpライブラリーに切り替えたくなるでしょう。

整数を素因数分解するための試行除算よりも優れたアルゴリズムがあり、試行除算を実装する上で示した方法よりも優れた方法もあります。しかし、それは始めるのに良い場所です。もっと読む準備ができたら、私のブログで「素数を使ったプログラミング」というエッセイをお勧めします。

于 2013-05-14T13:09:37.477 に答える