0

我正在尝试解决一个问题,但遇到分段错误,无法找到
问题所在,问题是您必须找到大于 227000 的第一个斐波那契数,这也是一个素数,称之为 X 并返回所有素数除数之和X+1

#include<iostream>
    int main(){
        int n = 227000;
        int prime[1000000];
        std::cout<<"lll";
        int i;
        for(i = 2; i<1000;i++){
            if(!prime[i]) continue;
            int j;
            for(j=i*i;j<1000000;j+=i){
                prime[j] = 0;
            }
        }
        int num = 1;
        int nextnum = 1;
        int newnum;
        while(1){
            newnum = num+nextnum;
            if(newnum>n && prime[newnum]) break;
            num = nextnum;
            nextnum = newnum;
        }
        int sum = 1;
        for(int i=2;i<1000000;i++){
            if(prime[i] && newnum%i==0){
                sum+=i;
            }
        }
        std::cout<<sum;
        return 0;

    }
4

3 回答 3

2

您可能会遇到分段错误的一个原因是由于在堆栈上放置了 100 万个整数而导致堆栈溢出。

另一个原因是素数未初始化,因此 while 循环可能会走得太远,访问超出数组限制的素数。

要解决此问题,您需要:

  1. 在堆上分配数组(或简单地将其更改为全局)
  2. 初始化您的素数数组以包含 1

如果 while 循环也保证终止,或者您可以超出边界访问素数数组,那就更好了。

#include<iostream>
int prime[1000000];
int main(){
    int n = 227000;
    std::cout<<"lll";
    int i;
    for(i = 2; i<1000000;i++)
      prime[i]=1;
    for(i = 2; i<1000;i++){
        if(!prime[i]) continue;
        int j;
        for(j=i*i;j<1000000;j+=i){
            prime[j] = 0;
        }
    }

    int num = 1;
    int nextnum = 1;
    int newnum;
    while(1){
        newnum = num+nextnum;
        if(newnum>n && prime[newnum]) break;
        num = nextnum;
        nextnum = newnum;
    }
    int sum = 1;
    for(int i=2;i<1000000;i++){
        if(prime[i] && newnum%i==0){
            sum+=i;
        }
    }
    std::cout<<sum;
    return 0;

}

更新

顺便说一句,第二个循环毫无意义地试图找到素数 newnum 的因子。

我怀疑问题实际上是要找到代码将更改为的数字(newnum + 1)的主要因素

    int sum = 0;
    for(int i=2;i<1000000;i++){
        if(prime[i] && (newnum+1)%i==0){
            sum+=i;
        }
    }
于 2013-01-18T20:39:46.690 回答
2

我会创建一个循环来生成斐波那契数,直到我发现比输入大一个。然后我会检查每个,看看它是否是素数。它比生成素数列表要快得多。

#include<iostream>
#include<math.h>

bool isPrime(int number)
{
    for (int i=2;i<=sqrt(number);i++)
        if ((number%i)==0) return false;

    return true;
}


int main(){

    int n = 227000;

    int index=1;
    int nums[2];
    nums[0]=0;
    nums[1]=1;
    int currentFib = 0;

    while (currentFib <=n || !isPrime(currentFib))
    {
        //Calculate the next fib
        index = (index+1)%2;
        nums[index] = nums[0]+nums[1];
        currentFib = nums[index];
        cout<<"Fibb "<<currentFib<<endl;
    }

    return currentFib;
}

代码返回 514229,它既是质数又是斐波那契数,并且大于 227000。

于 2013-01-18T20:59:13.883 回答
0

素数斐波那契数列在A005478 处。大于 227000 的最小素数斐波那契数是 514229。您可能会在我的博客上喜欢这篇文章。

于 2013-01-18T21:54:23.517 回答