3

さて、私が作成したこの関数は、エラトステネスのふるいアルゴリズムを使用して、すべての素数 <= n を計算します。この関数は、素数と素数の数をパラメーターに格納します。

関数が終了するとき、素数は、すべての素数 <= num を保持する、動的に割り当てられたメモリのチャンクを指している必要があります。 *count素数の数になります。

ここに私の機能がありますgetPrimes:

void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

    /* Starts crossing out non prime numbers starting with 2 because 1 
       is not a prime. It then deletes all of those multiples and 
       moves on to the next number that isnt crossed out, which is a prime. */
    for (; primenums < sqrt(num); primenums++)  //Walks through the array.
    {
        //Checks if that number is NULL which means it's crossed out
        if (sieve[primenums] != 0) {
            //If it is not crossed out it starts deleting its multiples.
            for (multiple = (sieve[primenums]); 
                 multiple < num; 
                 multiple += sieve[primenums]) {  
                //Crossing multiples out 
                //and decrements count to move to next number
                sieve[multiple + primenums] = 0;
                --(*count);
            }
        }
    }
    int k;
    for(k=0; k < num; k++)
        printf("%d \n", sieve[k]);

    printf("%d \n", *count);
    array = malloc(sizeof(int) * (num + 1));
    assert(array);
    (*array) = sieve;
}

さて、これが意図した出力と私の出力です。getPrimesご覧のとおり、関数内で何か問題が発生していますが、何が問題なのかわかりません。

意図した出力:

19以下の素数は8個

2 3 5 7 11 13 17 19  

私の出力:

2
3
0
5
0
7
0
0
0
11
0
13
0
0
0
17
0
19
0
0

これまでに人々が私に指摘した3つの問題は次のとおりです。

  1. 間違った削除プロセスif (sieve[multiple]) {配列ふるいインデックスにバイアスがあります
  2. (*array) = sieve;ちょうどmallocされたメモリをリークし*array、関数が戻ったときに存在しなくなるローカル変数を指すようにします-ダングリングポインターを取得します.
  3. if(sieve[i] != NULL)NULLではなく0を使用する必要があります。ポインターの配列がありません。

ただし、発見されたぶら下がっているポインター/メモリの問題を修正する方法がよくわかりません。それに加えて、出力の数字に0が追加されている理由がよくわからないため、コード内にエラーのあるものが他にあるかどうか疑問に思っていました...別の出力スタイルについて心配する必要はありません。余分な数字だけです. これで私を助けてくれてありがとう！

4

2 に答える 2

3 
void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

num-12 から までの数値に対して、要素の配列を宣言していますnum。大丈夫。

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

各スロットに関連付けられている番号を入力していますが、これも問題ありません。

     /* Starts crossing out non prime numbers starting with 2 because 1 is not a prime.
        It then deletes all of those multiples and 
        moves on to the next number that isnt crossed out, which is a prime. */
     for (; primenums < sqrt(num); primenums++) //Walks through the array.

おおまかに平方根で止まっています。それでいいのです。

        {
            if (sieve[primenums] != 0){ //Checks if that number is NULL which means it's crossed out

                   for (multiple = (sieve[primenums]); multiple < num; multiple += sieve[primenums])
                      //If it is not crossed out it starts deleting its multiples.
                   {  //Crossing multiples out and decrements count to move to next number
                            sieve[multiple + primenums] = 0;

ここで問題が発生しています。の場合にのみループを停止しますmultiple >= numが、 indexmultiple + primenumsに書き込みを行っているため、多くの場合、配列の末尾を超えています。たとえばnum == 19、 とprimenums == 1(3 の倍数を取り消します) を使用すると、最後の書き込みは index18 + 1ですが、最後の有効なインデックスは ですnum - 2 = 17。

ポイント 1 のインデックス バイアスが修正されました。しかし

                            --(*count);

ここでは無条件にデクリメントしています。*count以前のコードでは、まだ取り消し線が引かれていない場合にのみデクリメントしsieve[multiple]ました。それが正しい方法です。私は提案します

for(multiple = primenums + sieve[primenums]; multiple < num - 1; multiple += sieve[primenums]) {
    if (sieve[multiple]) {
         sieve[multiple] = 0;
         --(*count);
    }
}

もう少しシンプルに。

                   }
            }
        }
        int k;
        for(k=0; k < num; k++)
            printf("%d \n", sieve[k]);

の内容が存在sieveするかどうかに関係なく印刷しており、存在しない0も印刷しています。sieve[num - 1]成功する

for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        printf("%d\n", sieve[k]);
    }
}

素数のみを出力します。

            printf("%d \n", *count);
        array = malloc(sizeof(int) * (num + 1));
         assert(array);
         (*array) = sieve;
}

(*array) = sieveをに置き換えます

int i = 0;
for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        (*array)[i] = sieve[k];
        ++i;
    }
}

素数のみを に書き込み*arrayます。また、を割り当てる必要はありません(num + 1)*sizeof(int)が、そのためにのみ必要*count * sizeof(int)です。

于 2013-03-29T23:03:42.363 に答える
2

印刷している数字はふるいの数字なので、素数でないすべての数字は 0 に設定されています。次のように印刷してみてください。

for (k = 0; k < num; k++)
if (sieve[k] != 0)
{
        printf(" %d\n", sieve[k]);
}
printf("\n");

また、ローカル配列はスタック上にあり、関数の戻り時に使用できなくなるためsieve、パラメーターを介して返すべきではありません。array

于 2013-03-29T23:05:21.783 に答える