計算最近的素數到另一個數字沒有數組

Question

我有這個功課，但我不能完成它，因爲我只能使用關係運算符和if-else/while，我不能使用庫和方法，只有關係運算符和If或while時，我開始檢查如果限制的數字是素數，首先檢查If/by 2 3 5 7和11是否我用數字的平方根之前的每個數字嘗試百分比（以確定它是否爲是總理），但它只需要很多時間來做到這一點，我怎麼能用更少的時間來計算它，對於英語是一個難得的解釋抱歉。

Answer 1

沒有陣列，唯一的另一種選擇是有一些Eratosthenes篩選器（對於任何希望比試驗部門有更好的複雜性比原始性測試），我知道的是懶惰列表，它可以模擬發電機。在僞代碼，

primes = [2..] \ [[p*p, p*p+p, ...] for p in primes] 

與起點這成爲

primesFrom n = [n..] \ unionAll(
        [[s,s+p..] for each p in psq 
           where psq = primes upto (2 * sqrt(n)), 
           where s = div(n+p-1, p) * p]) 

，我們只希望帶着它產生的第一號。 工會這裏當然是一個訂購一，訂購，增加來源，以有序的方式產生其結果，一個接一個從較小的值到較大的值。

平方根的兩倍用於覆蓋範圍中最大的prime gap的想法。您可以通過查找範圍的主要差距的精確值來使其更加精確。 psq素數可以在發生器中與試驗師一同發現。

但是現在你需要維護這個發生器集合[s,s+p..]在某個地方，並且仍然禁止使用數組。

鏈表是一種可能性。它也可以效仿，與每個closures本地靜態存儲嵌套遞歸函數，創建它們對初始化鏈，像

  = [n..] \ 
       ([s1,s1+p1..] ∪ 
       ([s2,s2+p2..] ∪ 
        ([s3,s3+p3..] ∪ (.... [sk,sk+pk..] ....)))) 

你可以看到一個例子something just like this，在圍棋，here（和a faster one），儘管它實現的\ S（鏈沒有∪ S），

= (((....([n..] \ 
       [s1,s1+p1..]) \ 
        [s2,s2+p2..]) \ 
        [s3,s3+p3..]) \ ....) \ [sk,sk+pk..] 

這可能是乾脆做一個容易的事情。

該∪ s雖然可以安排in a tree，爲額外的complexity advantage。也許是一個有趣的項目。