2

数が素数かどうかを判断するプログラムを書こうとしています。私はそれをエラトステネスのふるいに基づいています。とにかく、私のプログラムは小さい数（15485863は動作します）で動作しますが、大きい数（例：17485863）を使用すると、セグメンテーション違反が発生します。unsigned long longを使用していますが、最大値を超えていないと思います。何を間違えたのかわかりません。よろしくお願いします！

#include <iostream>
#include <limits>

using namespace std;

bool soe (unsigned long long);

int main (void)
{
 unsigned long long x = 17485863;
 bool q = soe(x);

 cout << x << " is ";
 if(q)
  cout << "prime." << endl;
 else
  cout << "not prime." << endl;

 return 0;
    }

    bool soe(unsigned long long input)
    {
 unsigned long long arrayLength = input%2 + input/2;
 unsigned long long index = 2;
 unsigned long long greatestMult = 0;
 bool array[arrayLength];

 array[0] = true; //ignore true values in the array
 array[1] = true;
 do{
  array[index] = false;
 }while(++index < arrayLength);

 index = 2;

 do
 {
  if(input%index != 0)
  {
   greatestMult = input/index;
   while(index*greatestMult > arrayLength)
    greatestMult--;
   do
   {
    array[index*greatestMult] = true;
   }while(--greatestMult > 0);

   do
   {
    if(!array[index])
     break;
   }while(++index < arrayLength);

  }
  else
  {
   cout << endl << input << " is divisble by " << index << endl;
   return false;
  }
 }while(index < arrayLength);

 return true;
    }
4

3 に答える 3

3

longlongも変数を使用した自動配列のディメンション化もC++の一部ではないことに注意してください。これらはgccによって提供される拡張機能であり、移植性が問題になる場合は使用しないでください。

問題に対処するには、次のように配列のディメンションを設定します。

 bool array[arrayLength];

arrayLength値が大きすぎると、スタックオーバーフロー（したがってセグメンテーション違反）が発生します。代わりにstd::vectorを使用しますが、メモリは無限のリソースではないことに注意してください。

于 2010-02-20T19:03:16.923 に答える
1

24行目では次bool array[arrayLength]; のようになっています。このようにスタック上で配列を宣言することはできません。プログラムは29行目でクラッシュしています。new/deleteを使用してヒープ上でこれを宣言する必要があります。

この効果のための何か（私はそこに1つか2つのリークがあるかもしれませんが、あなたは考えを理解します）;

 //Beginning on Line 28
 bool *array = new bool[arrayLength];

 array[0] = true; //ignore true values in the array
 array[1] = true;
 do{
  array[index] = false;
 }while(++index < arrayLength);

 index = 2;

 do
 {
  if(input%index != 0)
  {
   greatestMult = input/index;
   while(index*greatestMult > arrayLength)
    greatestMult--;
   do
   {
    array[index*greatestMult] = true;
   }while(--greatestMult > 0);

   do
   {
    if(!array[index])
     break;
   }while(++index < arrayLength);

  }
  else
  {
   cout << endl << input << " is divisble by " << index << endl;
   delete [] array;
   return false;
  }
 }while(index < arrayLength);

 delete [] array;
 return true;
    }

出力

g++ -g test.cpp
gdb ./a.out
...clipped...
(gdb) run 
Starting program: /Users/nextraztus/a.out 
Reading symbols for shared libraries ++. done

17485863 is divisble by 3
17485863 is not prime.

Program exited normally.
(gdb)
于 2010-02-20T19:03:11.200 に答える
0

index * greatestMultがarrayLengthと等しくなる可能性があるため、配列の終わりを超えた最後の要素を上書きできます。

また、そのようにスタックに大きなアレイを割り当てると、オペレーティングシステムによっては問題が発生する可能性があります。一部のシステムはスタックをそれだけ拡張しますが、他のシステムは拡張できません。

于 2010-02-20T19:08:27.210 に答える