0 
#include <stdio.h>
main()
{
    long n=600851475143;
    int i,j,flag;
    for(i=2;i<=n/2;i++)
    {
        flag=1;
        if(n%i==0)//finds factors backwards
        {
            for(j=2;j<=(n/i)/2;j++)//checks if factor is prime
            {
                if((n/i)%j==0)
                    flag=0;
            }
            if(flag==1)
            {
                printf("%d\n",n/i);//displays largest prime factor and exits
                exit(0);
            }
        }    
    }
}

上記のコードはn = 6008514751. n = 600851475143ただし、その数値がまだ の範囲内であっても、では機能しませんlong。
機能させるにはどうすればよいですか？

4

5 に答える 5

5

潜在的な問題の 1 つは、iとjがintであり、 が大きいためにオーバーフローする可能性があることです (が よりも狭いとn仮定すると、多くの場合そうなります)。intlong

もう 1 つの問題は、n=600,851,475,143 の場合、プログラムがかなり多くの作業を行うことです (最大の要素は 6857 です)。完了するまでに長い時間がかかると予想するのは不合理ではありません。

于 2013-10-14T12:33:06.307 に答える
2

longs の代わりにsを使用しintます。さらに良いのは、uint64_tC99 以降に定義されている which を使用することです (Zaibis を認めてください)。これは、すべてのプラットフォームで 64 ビットの符号なし整数型です。(あなたが持っているコードは、一部のプラットフォームではオーバーフローします)。

次に、アルゴリズムをより迅速に機能させる必要があります。

素数のテストは非効率的です。すべての偶数を反復処理する必要はありません。素数を繰り返すだけです。あなたがテストしている数の平方根まで、そしてそれに等しい（あなたが現在行っている半分の方法ではない）.

素数はどこから取得しますか？さて、関数を再帰的に呼び出します。実際には、たとえば 65536 までの素数をキャッシュしたくなるでしょう。

于 2013-10-14T12:40:39.837 に答える
1

ISO/IEC 9899:TC3 より

5.2.4.2.1 整数型のサイズ

[...]

それらの実装定義の値は、同じ符号で示されているものと同じかそれ以上の大きさ (絶対値) でなければなりません。

[...]

— long int 型のオブジェクトの最小値

LONG_MIN -2147483647 // -(2^31 - 1)

— long int 型のオブジェクトの最大値

LONG_MAX +2147483647 // 2^31 - 1

編集：

申し訳ありませんが、これがあなたに伝えるべきことを追加するのを忘れていました。

ポイントは長く、言及した値を保持できる必要さえありません。標準では、符号付きで少なくとも4バイトを保持できる必要があるため、マシンが値を保持できる可能性があるためです。タイプ の変数で最大 2147483647 long。

于 2013-10-14T12:34:25.977 に答える
1

32 ビット マシンlongの範囲は-2,147,483,648 ～2,147,483,647で、64 ビット マシンの範囲は-9,223,372,036,854,775,808～9,223,372,036,854,775,807です。 OP がコメントで言ったように、彼は 32 ビットを使用しており、 の範囲に収まらないため、範囲外になります。
600851475143long

于 2013-10-14T12:39:09.693 に答える
0

n.. に変更してみてlong long int、i,j を long に変更してみてください

編集: n を次のように定義します:

long long int n = 600851475143LL;

LL- は long long 型を強制する接尾辞です ...

于 2013-10-14T12:41:23.767 に答える