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

入力よりも大きいフィボナッチ数が見つかるまで、ループを作成してフィボナッチ数を生成します。それから私はそれが素数であるかどうかを確認するためにそれぞれをチェックします。素数のリストを生成するよりもはるかに高速です。

#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 に答える
2

セグメンテーション違反が発生する理由の 1 つは、スタックに 100 万個の整数を配置するためにスタック オーバーフローが発生することです。

もう 1 つの理由は、素数が初期化されていないため、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;

}

アップデート

ところで、2 番目のループは無意味に素数 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 に答える
0

素数フィボナッチ数はA005478で与えられます。227000 より大きい最小の素数フィボナッチ数は 514229 です。私のブログでこのエントリをお楽しみください。

于 2013-01-18T21:54:23.517 に答える