需要幫助免費帕斯卡爾eratosthenes篩

-2

n < = 10^6;

n整數數組：ai..an（ai < = 10^9）;

找到所有素數。

他說了一些關於eratosthenes的篩選，我也讀了它，也分析了輪子分解，但我仍然無法弄清楚如何讓程序（fpc）在1s中運行。因爲我知道這是不可能的，但仍想知道你的意見。和輪子分解，一個2 * 3的圓將25視爲一個素數，我想問一下，是否有辦法找出錯誤處理的第一個數字作爲素數。例如：2 * 3 * 5圈，如何找到第一個合成號碼作爲最小號碼？請幫助..對不起英語不好。

來源

2014-10-08 dang hoang

看看[Wikipedia]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes），還有一個篩子的實例。這比車輪更容易。 – joe 2014-10-08 05:26:22

免費Pascal在demo/text/eratos.pp中附帶基本篩選示例輪子分解可能是分配的關鍵。顯示您已有的內容可以使評論更容易。 – 2014-10-08 12:20:07

Eratosthenes的一個適當的篩子應該在大約一秒內找到不到10億的素數;這是可能的。如果您向我們展示您的代碼，我們很樂意幫助您找到問題所在。

不是由2,3,5輪標最小的複合材料是49：下一個最大的黃金沒有車輪的成員爲7，7 * 7 = 49

來源

2014-10-08 12:40:46 user448810

我現在做到了，它會在幾毫秒內找到1000000的質數，而不顯示所有這些數字。聲明一個n + 1布爾數組（如果它是從零開始的）。在開始的第0和第1個元素是假的，其他都是真的（假不是素數）。該算法看起來像這樣：

i = 2; 
while i * i <= n 
    if a[i] == true 
     j = i * i; 
     while j < n 
      a[j] = false; 
      j = j + i; 
    i = i + 1;

在一個循環中的條件爲i * I < = N，因爲你開始搜索我* I（小素數比用其他的素數的一個已經找到），這樣方我的根不能大於n。您刪除所有與質數相乘的數字，直到n。時間複雜度爲O（n log log n）。如果要顯示素數，則顯示索引，其中數組中的值爲true。

因式分解是有用的，如果你想找到例如所有從0到n的半值（兩個素數的乘積）。然後，您可以找到從0到n/2的所有最小素數因子，並檢查每個數字是否具有素數除數，並且數字除以其素因數除以零除數。如果是這樣 - 它是一種半成品。我的程序是這樣寫的，它的計算速度比首先找到所有素數快8倍，然後將它們相乘並將結果保存在一個數組中。

來源

2014-10-10 22:09:10

需要幫助免費帕斯卡爾eratosthenes篩

回答

相關問題