4 
#include <stdio.h>
#include <math.h>

// #define LIMIT 600851475143
int isP(long i);
void run();
// 6857
int main()
{
    //int i = 6857;
    //printf("%d\n", isP(i));
     run();
}

void run()
{
long LIMIT = 600851475143;
// 3, 5
// under 1000

long i, largest =1, temp=0;
for(i=3; i<=775147; i+=2)
{
    temp = ((LIMIT/i)*i);
if(LIMIT == temp)
    if(isP(i)==1)
            largest = i;
}
printf("%d\n",largest);
}

int isP(long i)
{
long j;
for(j=3; j<= i/2; j+=2)
    if(i == (i/j)*j)
        return 0;

return 1;

}

興味深い問題に出会いました。上記のように、このコードは LIMIT の最大の素数を計算するように設計されています。上記のプログラムは 29 という答えを出しましたが、これは正しくありません。

一方、奇跡的に、LIMIT 値を (長いと宣言する代わりに) 定義すると、正しい値である 6857 が得られました。

誰かが理由を理解するのを手伝ってもらえますか? どうもありがとう！

4

6 に答える 6

3

多くのlongプラットフォームの は 4 バイトの整数であり、 でオーバーフローし2,147,483,647ます。たとえば、Visual C++ の Data Type Rangesページを参照してください。

を使用する#defineと、コンパイラは非常に大きな数を保持できるより適切な型を自由に選択できます。これにより、正しく動作し、期待する答えが得られます。

ただし、一般的には、データ型について明示し、可能であれば、コンパイラやプラットフォーム固有の動作を必要とせずに数値を正しく表すデータ型を選択することをお勧めします。

于 2013-03-06T17:11:28.207 に答える
1

次のような式を入力すると:

(600851475143 + 1)

コンパイラはこれらの定数の両方をlong long、計算を実行するのに十分な大きさの適切な型 (あなたの場合のように) に自動的にプロモートするため、すべて問題ありません。このようにして、必要な数の表現を行うことができます。しかし、あなたが書くとき：

long n = 600851475143;

long longコンパイラは a (または定数が暗黙的に変換されるもの) を aに割り当てようとしlongますが、これはあなたの場合に問題を引き起こします。コンパイラはこれについて警告する必要があります。たとえば、gcc は次のように述べています。

warning: overflow in implicit constant conversion [-Woverflow]

もちろん、 alongがその値を保持するのに十分な大きさである場合、定数は と同じlongかそれより小さいサイズの型になるため、問題はありません。

于 2013-03-06T17:24:39.373 に答える
1

ここで数値型の問題が疑われます。

#defineはプリプロセッサ ディレクティブであるためLIMIT、コンパイラを実行する前にコード内のその番号に置き換えられます。これにより、コンパイラがその数値を必要に応じて解釈するための扉が開かれたままになりますlong。

あなたの場合、longおそらく十分な大きさではないので、コンパイラは を使用するときに別のものを選択します#define。動作に一貫性を持たせるには、適切な範囲があることがわかっている型を指定し、コンパイラによる正確な推測に依存しないようにする必要があります。

また、コンパイラで完全な警告をオンにする必要があります。この種の問題を検出できる場合があります。

于 2013-03-06T17:09:49.523 に答える
0

制限のタイプを「long long」に置き換えてみてください。このままでは、ぐるぐる回ります（制限を長めに印刷してみてください）。プリプロセッサはそれを認識し、正しい型を使用します。

于 2013-03-06T17:14:37.760 に答える
0

コードは基本的に次の 2 つの可能性に絞り込まれます。

long LIMIT = 600851475143;
x = LIMIT / i;

対。

#define LIMIT 600851475143
x = LIMIT / i;

最初のものは、定数を にキャストするのと同じですlong:

x = (long)600851475143 / i;

2番目のものは次のようにプリコンパイルされます。

x = 600851475143 / i;

ここに違いがあり600851475143ます。コンパイラのlong型には大きすぎるため、それにキャストするlongとオーバーフローしておかしくなります。しかし、それが除算で直接使用された場合、コンパイラはそれが a に収まらないことを認識しlong、自動的にそれをlong longリテラルとして解釈し、iがプロモートされ、除算が a として行われますlong long。

ただし、ほとんどの場合アルゴリズムが機能しているように見えても、他の場所でオーバーフローが発生しているため、コードが正しくないことに注意してください。これらの大きな値を保持する可能性のある変数は、 として宣言する必要がありますlong long。

于 2013-03-06T17:26:52.457 に答える
0

（これによると 2147483647 ）600851475143よりも大きいためでしょう。LONG_MAX

于 2013-03-06T17:10:42.160 に答える