SPOJ PRIME1：RTE;有沒有一種方法來避免動態數組？

我讀了關於Eratosthenes算法的Sieve，並試圖實現它，代碼編譯時沒有任何錯誤，但我得到了空白輸出。下面是代碼： -SPOJ PRIME1：RTE;有沒有一種方法來避免動態數組？

#include <stdio.h> 
#include <stdlib.h> 
#define limit 100000 
int main() 
{ 
int prime[limit]; 
int i,j,t; 
int n,m; 
scanf("%d",&t); 
while(t--) 
{ 
scanf("%d%d",&m,&n); 
for(i=0;i<=n;i++) 
{ 
    prime[i]=1; 
} 
prime[0]=0; 
prime[1]=0; 
for(i=2;i<=n;i++) 
{ 
    if(prime[i]==1) 
    { for(j=2;i*j<=n;j++) 
       prime[i*j]=0; 
    } 
} 
for(i=m;i<=n;i++) 
{ 
    if(prime[i]!=0) 
     printf("%d\n",i); 
} 
} 


return 0; 
}

來源

2015-12-12 Aniket Sanadhya

的問題是你的篩數組的大小：它必須足夠大，可拉伸至您要處理的最高數量，而不是項目的數量，你希望找到。

您的實施適用於查找最多100個素數，而不是前100個素數。由於質數100是541，您需要將大小更改爲542：

int prime[542];

你也需要做出n -the-數的，素數和n -the-最高貸之間的區別你碼。我建議保留n作爲您希望查找的素數的計數，並使用#define SIZE 542來確定陣列的大小。訪問數組元素時，請確保使用< SIZE而不是<= SIZE。

來源

2015-12-12 14:47:36 dasblinkenlight

是的，但我只是測試我的實現與默認編號。說100，後來我會增加陣列的大小，但即使是100也有一個空白輸出 –

@AniketSanadhya 100產生未定義的行爲。請嘗試修復。 – dasblinkenlight

它不應該給出空白輸出。應該給出'1'的列表。除非i * j == 100的素數[i * j] = 0會覆蓋n。 – marom

一件重要的事情：你不必打印素數[我]（這是1），但我。這樣你會得到一個更有趣的輸出...

來源

2015-12-12 14:53:37 marom

謝謝，它的工作 –

需要再次幫助.. –

要獲得極限，請看看https://en.wikipedia.org/wiki/Prime-counting_function – marom

SPOJ PRIME1：RTE;有沒有一種方法來避免動態數組？

回答

相關問題