0

したがって、最大の素因数でプロジェクト オイラー問題を解決するプログラムを作成しようとしていますが、コードが構造的に正しいことはわかっていますが (13195 の例を含め、より小さな数に対して正しい答えを返す限り)、私は解決すべき数字 600851475143 を入力すると、セグメンテーション違反が発生し続けます。コードは次のとおりです。

#include <stdio.h>
#include <math.h>

main(){
    int number,a,b,c,i,j,n,gpf;
    printf("Input number to analyze: ");
    scanf("%d",&number);
    a = number/2;
    printf("%d\n",a);
    int* primesieve = new int[a+1];               /*IMPORTANT LINE*/
    for (i=0;i<a+1;i++){
        primesieve[i] = 1;
    }
    for (j=2;j<=a;j++){
        if (primesieve[j] == 1){
            for (c=2;j*c<=a;c++){
                primesieve[j*c] = 0;
            }
        }
    }
    for (n=2;n<=a;n++){
        b = number/n;
        printf("%d\n",b);
        if (number % n == 0){
            if (primesieve[b] == 1){
                gpf = b;
                n = a+1;
            }
        }
    }
    delete[] primesieve;
    printf("The greatest prime factor of %d is %d.\n",number,gpf);
}

この問題は、プライム シーブの配列の初期化に起因します。これは、その行以降のすべての行を省略しても問題が発生したためです。最初に次のコードを使用して配列を宣言しましたが、1,000 万という低い値に対してセグメンテーション違反が返されました。

int primesieve[a+1];

このサイトで解決策を探したところ、動的配列割り当てに変更されましたが、これで 1,000 万の問題は解決しましたが、大幅に大きな値では解決しなかったようです。私が気づいた他の解決策は、malloc() の使用または main() の外側で配列を静的に宣言することについて言及していましたが、率直に言って、私の入門プログラミング クラスでは malloc() についてほとんど言及されておらず、宣言に至るまでのコードがの配列を main() に含める必要がありました。(参考: Cで大きな配列を作成するときのセグメンテーション違反と、配列を初期化するときのセグ違反.) これはかなり単純な問題だと確信していますが、私は比較的新しいプログラマーであり、メモリの割り当てについてよく理解していません。

4

2 に答える 2

0 
600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB

つまり、5TB の RAM がない限り、このコードは常にクラッシュします。

ふるいにビットマップを使用すると、もう少し耐えられるようになります。たとえば、数値ごとに 1 ビットを使用し、偶数をマッピングしない場合は、RAM の600851475143 / 8 / 2=のみが必要です。35GBまだたくさんありますが、ハードウェアにいくらかのお金があれば実現可能です.

于 2013-10-19T09:42:20.040 に答える
0

あなたの経験は、物理的な限界とコンパイラの精度に関連しています。最初の試行、スタックに配列を割り当てる

int primesieve[a+1];

ほとんどのシステムでは、スタックはヒープに比べてサイズがかなり制限されているため、すぐに失敗しました。

ヒープへの割り当て

int* primesieve = new int[a+1];

より多くのスペースが得られますが、アドレス指定可能なメモリにはまだ制限があります。さて、600851475143 は、たとえ 2 で割ったとしても、非常に大きな数です。 のサイズintが 4 バイトであると仮定すると、本当にそれだけの量のメモリをアドレス指定できるのだろうかと疑問に思うかもしれません。32 ビットの場合、2^32 = 4294967296 バイトをアドレス指定できます。

于 2013-10-19T10:00:01.193 に答える