-1（0xFFFFFFFF）の戻り値を取得するのはなぜですか？

Question

私は非常に最近、最初のコーディング言語であるcを学び始めました。私はProject Eulerから問題3を解決しようとしており、そうするためにこれを書きました。このコードは、600851475143, の最大の素因数を識別するためのものですが、私は理解できない奇妙な戻り値を得ています。誰でも知っている理由は？

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
    int i = 1, a = 0, prime = 0; 
    for(i = 1; i < 600851475143; i += 2) { 
     for(a = 0; a <= i/2; a++) { 
      if(i % a == 0) { 
       break; 
      } 
      if(a = i/2) { 
       if(600851475143 % i == 0) { 
        prime = i; 
       } 
      } 
     } 
    } 
    printf("%d\n", prime); 
    return 0; 
} 

Answer 1

あなたの問題はオーバーフローと呼ばれています。使用可能なメモリが限られているため、すべてのデータ型には制限があります。平均的な現代的なコンピュータ上のintは、通常、最大で2,147,483,647になります（警告：私は通常言った）。事実はもう少し複雑です。とにかく、上限を超えています。

int（または符号付き整数データ型）がオーバーフローすると、何らかの表現に関連する問題のために負になります。理由の詳細については、の補数表現をご覧ください。

これを修正するには、より広い範囲のデータ型を使用します。 long longは9,223,372,036,854,775,807になります。整数リテラルはlong longとしてマークすることも必要であること

注、そうでない場合、彼らはあまりにもオーバーフローします：あなたはlong longによってサポートされている範囲よりも大きな整数値が必要な場合は

for(i = 1; i < 600851475143LL; i += 2) 

を（していないようですあなたの運命から外れている：あなたはそれに対処するためにいくつかの巧妙な方法を見つける必要があります。

何か他のものは、コードを実行したときに0で除算されていることです。これがオーバーフローに関連するかどうかはわかりません。

Answer 2

0で除算する（または%0を試す）。これはの未定義の動作（UB）で、-1の戻り値を説明することができます。 UB - であれば何でもが起こる可能性があります。 これが修正されるまで、残りのコードは重要ではありません。

for(a = 0; a <= i/2; a++) { 
    //  v---- a is zero! 
    if(i % a == 0) { 

コードはおそらく、i/2で2

// for(a = 0; a <= i/2; a++) { 
for(a = 2; a <= i/2; a++) { 

よりもむしろエンドとして√600851475143の端を開始する必要があり、それが早くずっとです。

  v-------------------v Same a <= sqrt(600851475143) without FP or overflow 
for(a = 2; a <= 600851475143/a; a++) { 

その他の問題もあります。 if(a = i/2)可能性が高いだけでなく600851475143範囲を持っているので、i < 600851475143は常に真である@Tom Karzes

intを参照してください。一般的なコンパイラ警告がこれを発行します。時間を節約するために警告を完全に有効にしてください。@iBug

warning: comparison is always true due to limited range of data type [-Wtype-limits] 

---

擬似コードソリューション

int main(void) { 
    wide_enough_type n = 600851475143; 
    wide_enough_type factor = 1; 
    try each i starting at 2 and until i*i <= n 
    repeat as long as n divides into i with no remainder 
     make n smaller by diving it by i 
     save i as factor 
    save the larger of (n, factor) as factor 
    printf("Greatest factor: %some_type_specifier\n", factor); 
}