C - 從特定的大範圍獲取素數

#include <stdio.h> 
#include <math.h> 
#define UPPER_LIMIT 2147483647 
void sieve(unsigned long int n, unsigned long int primes[]); 
main() 
{ 
    unsigned long int low, up, steps; 
    unsigned long int v[UPPER_LIMIT]; 
    sieve(UPPER_LIMIT, v); 
    scanf("%ld\n",&steps); 
    for (unsigned long int i=0;i<steps;i++){ 
     scanf("%ld %ld\n",&low,&up); 
     for(unsigned long int j=low; j<up; j++){ 
      if (v[j] == 1){ 
       printf("%ld\n",j); 
      } 
     } 
    } 
} 
void sieve(unsigned long int n, unsigned long int primes[]) 
{ 
    for (unsigned long int i=0;i<n;i++){ 
     primes[i]=1; 
    } 
    primes[0]=0,primes[1]=0; 

    for (unsigned long int i=2;i<sqrt(n);i++) { 
     for (unsigned long int j=i*i;j<n;j+=i){ 
      primes[j] = 0; 
     } 
    } 
}

我試圖解決從特定範圍打印素數的問題。起初scanf我們得到要審查的案件數量。範圍由stdin的下一行給出，例如（1 10）上限值可以在最大值2147483647處。我使用Erastostenes的Sieve來查找素數。之後，我想printf素數按升序排列。不幸的是，我得到一個運行時錯誤，我認爲這是因爲我想創建的非常大的數組。我需要關於該問題的可能解決方案的建議。標準輸入的C - 從特定的大範圍獲取素數

實施例：

1 
1 10

標準輸出的實施例：

2 
3 
7

來源

2017-04-26 deadal

'unsigned long int v [UPPER_LIMIT];'可能太大了。嘗試用'malloc'創建。 –

從什麼時候5不是1到10之間的素數？ –

全局聲明的素數陣列最大尺寸。
您可以使用矢量來存儲素數（C++容器）。
並且陣列大小最多可以是10^7到10^8，您不能聲明unsigned long int v[2147483647];這個大陣列您也無法通過這種方法解決問題:)。

來源

2017-04-26 19:36:20 unreleased

您試圖創建一個局部變量，它在大多數實現中位於堆棧上，具有非常大的大小。使用類型爲unsigned long的2G元素，您最有可能查看8 GB或16 GB。這對堆棧來說太大了。

將此變量作爲全局創建。這樣它就不會生活在堆棧上，而是依賴於數據部分（取決於實現）。

此外，由於此數組僅分配值0和1，因此將數組的類型更改爲char，因此每個元素只使用1個字節。這將爲您節省大量的內存。

來源

2017-04-26 19:56:01 dbush

使用unsigned long陣列僅存儲0或1沒有意義。

你只需要2147483647/8位來存儲你所需要的全部信息，所以你應該申報最多2147483647/8 + 1字節數組：

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char primes[SIZE];

甚至更好，通過堆分配：

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char *primes = (unsigned char*)malloc(SIZE);

陣列初始化變爲：

for (unsigned i = 0; i < SIZE ; i++){ 
    primes[i] = 1; 
}

可以使用按位運算符>>,<<和&來訪問陣列的各個位。實施這個只是一個練習，因爲這看起來像大學演習。

來源

2017-04-26 19:56:59

如果你使用的是C++，你可以使用專門的'std :: vector '作爲一個易於使用的實現，其中每個索引都被存儲爲一個單獨的位。 –

C - 從特定的大範圍獲取素數

回答

相關問題