0 
/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/

#include <iostream>
#include <string>
#include <cmath>

using namespace std;


int main()
{
    unsigned long num = 600851475143;
    unsigned long i;
    long double root = sqrt(num);
    long double tempRoot = 0;
    unsigned long factor = 0;
    unsigned long largest = 0;

    for (i=2; i<root; i++)
    {
        if (num%i == 0)
        {   
            num = num/i;
            factor = i;
            cout << factor << endl;

            if (factor > largest)
                {
                    largest = factor;
                }
        }
    }

    cout << largest << endl;    

return 0;
}

偶然にも 600851475143 の約数がすべて素数であるため、この解決策は機能します。しかし、コードをデバッグするときに、変数 num (=600851475143) にさまざまな値を入力していました。たとえば、135 と入力すると、非素数を含むすべての要素が表示されました。因数の素数チェッカーを追加するにはどうすればよいですか? ここでネストされた if 内で使用したのと同じ方法を使用しようとしましたが、惨めに失敗しました。どんな助けでも大歓迎です。

また、一部の変数の場合に不必要に大きな変数タイプを使用しているかどうかを示してください。

ありがとう。

4

1 に答える 1

1

素数チェックを行う必要はありません。因数分解しているときは、数が分割されなくなるまで候補を分割し続けるようにしてください。これはコードで行うのは非常に簡単です: を に変更するだけif (num%i == 0)ですwhile (num%i == 0)。

于 2012-10-02T00:20:58.157 に答える