在我的 Fibonacci C++ 中找不到分段错误的原因；代码

Question

我的代码出现段错误。我不明白为什么。这可能与我制作的“fermatPrimeTest()”函数有关。

#include <iostream>
#include <cmath>
#include <cstdlib>
#include "fib.h"
using namespace std;

bool fermatPrimeTest( unsigned long int p )
{
  if ( p % 2 == 0 ) { // if even
    return false;
  } 
  else if ( p == 1 || p == 2 || p == 3 ) { // if 1, 2, or 3
    return true;
  }
  unsigned long a = 2 ; // just give it an initial value, make it happy
  for ( int i=0 ; i < 3 ; i++) {
    if (GCD(a, p-1) != 1) {
      a = rand() % (p-1) + 1;
    }
    // cout << "a=" << a << " ,p=" << p << GCD(a, p-1) << endl;
  }
  return true;
}

int GCD(unsigned long int a, unsigned long int b) {
  while( 1 ) {
    a = a % b;
    if( a == 0 )
      return b;
      // cout << "GCD-b=" << b << ", GCD-a=" << a << endl;

    b = b % a;

    if( b == 0 )
      return a;
      // cout << "GCD-a=" << a << ", GCD-b=" << b << endl;
  }
}

// fills array with Fibonacci primes
// returns number of primes
unsigned long findFibonacciPrimes (unsigned long lowerBound,
                                   unsigned long upperBound,
                                   unsigned long result[])
{  
  int i = 0;  //counter
  unsigned long maxElements = upperBound - lowerBound + 1;  // there can be no more array elements than this

  /*
  The array result is guaranteed to have enough space to store all the numbers found. 
  Your program will crash if it attempts to write past the end of the array, and no 
  marks will be awarded for any tests in which this occurs. You are also guaranteed that 
  1 < lowerBound < upperBound < 3,000,000,000.
  Every F_n that is prime has a prime  index n, with the exception of F_4=3. 
  However, the converse is not true (i.e., not every prime index p gives a prime F_p). 
  */

  unsigned long int one = 0, two = 1, three = one + two;   // element x-2, x-1, and x for Fib sequence
  result[i++] = 0;
  result[i++] = 1;

 while ( lowerBound < three < upperBound ) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }
  return sizeof result / sizeof result[0];   // return size of array TODO!
}
int main() {
  unsigned long result[100];
  findFibonacciPrimes(1,100,result);
}

Answer 1

第 67 行：

 while ( lowerBound < three < upperBound ) {

许多语言不正确支持这样的链式比较。您需要这样写：

 while ( lowerBound < three && three < upperBound ) {

---

在 C++ 中，lowerBound <三< upperBound 被解释为 (lowerBound <三) 上限。表达式 lowerBound < Three 始终会导致 0（假）或 1（真），因此此 while 循环将始终成功，因为 upperBound 为 100。

这会导致行 < code>result[i++] = 3; 运行超过 100 次，因为斐波那契素数有 100 多个。但result的大小只有100。当i≥100时，程序将写入无效的内存区域，这会导致分段错误。

---

正如安德烈斯在评论中所说，你最好使用 a 向量，例如

#include <vector>
...
std::vector<unsigned long> findFibonacciPrimes(unsigned long lowerBound,
                                               unsigned long upperBound) {
   std::vector<unsigned long> result;
   result.push_back(0);
   result.push_back(1);  // note that 0 and 1 aren't primes.
   ...
   while (lowerBound < three && three < upperBound ) {
      if ( fermatPrimeTest(three) ) {
        result.push_back(three);
      ...
   return result;
}

int main () {
   std::vector<unsigned long> result = findFibonacciPrimes(1, 100);
   // use result.size() to get the number of items in the vector.
   // use result[i]     to get the i-th item.
}

Answer 2

我看到很多潜在的错误。

这是导致崩溃的错误：

鉴于您的主循环：

 while ( lowerBound < three < upperBound ) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }

我认为您确实应该这么说，以保护您的数组长度，而与算法停止无关。

 while ((i < maxElements) && (lowerBound < three) && (three < upperBound)) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }

现在我的批评的其余部分：
给定这一行：

return sizeof result / sizeof result[0];   // return size of array TODO!

sizeof(result) 将始终返回 4（或 64 位编译上的 8），因为您计算的是指针的大小而不是静态数组的 sizeof。编译器不知道该指针实际上是一个静态大小的数组。

你可能想说：

return i;