C程序停止響應大輸入

Question

我（重新）學習C並在本書中，我正在關注我們正在討論的數組，並且本書給出了一個用於找到前n個素數的算法;我自己是一位數學家，還有一些熟練的程序員，他用幾種語言決定使用不同的算法（使用Eratosthenes篩選）來獲得前n個素數。好的算法運行得很好，我的工作，甚至對於中等大的輸入，即前50,000個素數需要一點運行，但是沒有問題。然而，一旦開始出現一個80,000的素數就會彈出一個窗口，說程序沒有響應，並且需要退出，所以我確保讓素數變量​​無符號long long int，所以我應該仍然在他們的價值觀的可接受範圍內。我在網上做了一些粗略的瀏覽，其他有大量輸入問題的人收到了在main之外創建變量的建議，以使它們成爲全局變量。我嘗試了一些可以立即放到外面的變量，但這並沒有解決問題。可能我需要把我的數組isPrime或主要外部的素數？但我真的不知道該怎麼做，因爲我所有的工作都是主要的。我知道我應該用單獨的函數來完成這個工作，但是我只是寫了它，但是如果我把所有的東西都移動到不同的函數中，我的數組仍然不是全局的，所以我不知道如何解決這個問題。

我試着讓它們靜態或外部，試圖讓它們離開堆棧內存，但自然不能工作，因爲它們數組根據輸入更改大小，並隨時間而改變。

代碼：

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

unsigned long long int i,j; 
unsigned long long int numPrimes,numPlaces; 




int main(void) 
{ 
    bool DEBUG=false; 

    printf("How many primes would you like to generate? "); 
    scanf("%llu",&numPrimes); 

    // the nth prime is bounded by n*ln(n)+n*ln(ln(n)), for n >=6 
    // so we need to check that far out for the nth prime 
    if (numPrimes>= 6) 
     numPlaces = (int) numPrimes*log(numPrimes)+ 
          numPrimes*log(log(numPrimes)); 
    else 
     numPlaces = numPrimes*numPrimes; 

    if(DEBUG) 
     printf("numPlaces: %llu\n\n", numPlaces); 

    // we will need to check each of these for being prime 
    // add one so that we can just ignore starting at 0 
    bool isPrime[numPlaces+1]; 

    // only need numPrimes places, since that is all we are looking for 
    // but numbers can and will get large 
    unsigned long long int primes[numPrimes]; 

    for (i=2; i<numPlaces+1;i++) 
     isPrime[i] = true; // everything is prime until it isn't 

    i=2; // represents current prime 
    while (i < numPlaces + 1) 
    { 
     for (j=i+1;j<numPlaces+1;j++) 
     { 
      if (isPrime[j] && j%i ==0) // only need to check if we haven't already 
      { 
       isPrime[j] = false;// j is divisibly by i, so not prime 
       if(DEBUG) 
       { 
        printf("j that is not prime: %llu\n",j); 
        printf("i that eliminated it: %llu\n\n",i); 
       }//DEBUG if 
      }//if 
     }//for 

     // ruled out everything that was divisible by i, need to choose 
     // the next i now. 

     for (j=i+1;j<numPlaces+2;j++)// here j is just a counter 
     { 
      if (j == numPlaces +1)// this is to break out of while 
      { 
       i = j; 
       break; 
      }// if j = numPlaces+1 then we are done 
      else if (isPrime[j]==true) 
      { 
       i = j; 
       if (DEBUG) 
       { 
        printf("next prime: %llu\n\n",i); 
       }//DEBUG if 
       break; 
      }//else if 
     }// for to decide i 
    }//while 

    // now we have which are prime and which are not, now to just get 
    // the first numPrimes of them. 
    primes[0]=2; 
    for (i=1;i<numPrimes;i++)// i is now a counter 
    { 
     // need to determine what the ith prime is, i.e. the ith true 
     // entry in isPrime, 2 is taken care of 
     // first we determine the starting value for j 

     // the idea here is we only need to check odd numbers of being 
     // prime after two, so I don't need to check everything 
     if (i<3) 
      j=3; 
     else if (i % 2 ==0) 
      j = i+1; 
     else 
      j = i; 

     for (;j<numPlaces+1;j+=2)// only need to consider odd nums 
     { 
      // check for primality, but we don't care if we already knew 
      // it was prime 
      if (isPrime[j] && j>primes[i-1]) 
      { 
       primes[i]=j; 
       break; 
      }//if, determined the ith prime 
     }//for to find the ith prime 
    }//for to fill in primes 

    // at this point we have all the primes in 'primes' and now we just 
    // need to print them 

    printf(" n\t\t prime\n"); 
    printf("___\t\t_______\n"); 

    for(i=0;i<numPrimes;i++) 
    { 
     printf("%llu\t\t%llu\n",i+1,primes[i]); 
    }//for 

    return 0; 
}//main 

我想我可能只是避免了素數排列，只是使用isPrime的指標，如果這將有助於？任何想法將有助於感謝！

Answer 1

你的問題是在這裏，在VLA的定義（「變長數組」 ，而不是「甚大陣」）

bool isPrime[numPlaces+1]; 

該程序沒有在本地區域有足夠的空間數組變量isPrime當numPlaces很大時。

你有兩個選擇：

1. 宣佈了「足夠大」尺寸的陣列的主要功能之外，忽略了額外的空間
2. 使用其他區域用於存儲陣列malloc()和朋友

選項1

#include <stdio.h> 

unsigned long long int i,j; 
bool isPrime[5000000]; /* waste memory */ 

int main(void) 

ö ption 2

int main(void) 
{ 
    bool *isPrime; 

    // ... 

    printf("How many primes would you like to generate? "); 
    scanf("%llu",&numPrimes); 

    // ... 

    // we will need to check each of these for being prime 
    // add one so that we can just ignore starting at 0 
    isPrime = malloc(numPrimes * sizeof *isPrime); 

    // ... use the pointer exactly as if it was an array 
    // ... with the same syntax as you already have 

    free(isPrime); 
    return 0; 
} 

Answer 2

您分配的數組是堆棧變量（極有可能），並且堆棧大小是有限的，因此只要達到特定的大小閾值，就可能覆蓋重要的東西，導致程序崩潰。嘗試使用一個用malloc分配的動態數組來存儲篩。