注意： @David_Burnham的挑戰作品已在截止日期之前提交，但被我的電子郵件系統隔離。我只是在原始部落格文章發布後才發現這一點。我正在更新結果以反映基於新條目的變更。
感謝所有為挑戰 2 提交程式碼的人。下表給出了挑戰每個部分的結果。 是質數運行了三次，分別是 1000 個不能被 5 整除的 5 位隨機奇數、不能被 5 整除的 8 和 9 位奇數以及不能被 5 整除的 12 到 15 位奇數。挑戰賽的積分如下：第一名得 1.5 分，第二名得 1 分，第三名得 0.5 分。也給出了最快提交的時間（以秒為單位）。
@leelaim isPrime(Small) 的時間與 JMP 工作人員的任何時間一樣快（+3 分）。 @landon isPrime(Big) 腳本使用 Parallel Assign 函數來提高速度。其中兩個條目使用命名空間快取了獲取質量數的結果。當需要多次存取結果時，這種方法很有用（但是運行時間是基於未快取的結果）。所有這四個條目均已包含在下文中。
以下是兩次挑戰後的排行榜：
挑戰 3 將於 6 月 1 日星期三發布。
挑戰 2 要求用兩種可能的方法來尋找質數。給定一個正整數值n ，你必須找到：1) n個質數或 2) n以下的所有質數。讓我們從 2) 開始，因為它更容易實現。尋找質數最簡單的方法是試除法。以 2 作為候選數和一個空素數集開始，檢查目前質數集中是否有任何數可以整除候選數。如果不是，則將其新增至素數集合並繼續下一個候選。由於開始的質數集合中沒有任何內容，因此添加了 2。檢查 3，它不能整除 {2} 中的任何數，因此被加到素數集。然而，數字 4 確實除掉了 {2,3} 中的某個數字，但並沒有將其相加。下面顯示了一個範例實作。
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
這種方法有幾個優點：它很容易理解，程式碼簡潔，並且可以輕鬆適應素數查找挑戰。不幸的是，它非常慢。尋找 100,000 以下的質數花了我 19.43 秒。
稍微複雜一點的方法是使用篩子。不是測試數字是否為質數，而是篩選出不屬於質數的數字。最古老和最著名的篩法是埃拉托斯特尼篩法。首先假設一切都是質數。以 2 作為第一個質數，找出所有能整除它的數字並將它們從素數集中刪除。繼續處理仍在素數集中的下一個數字。下面是未最佳化的版本。
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
最明顯的優勢就是速度。我找到 100,000 以下的所有質數的時間是 0.2811 秒，大約快 70 倍，而找到 1,000,000 的所有質數的時間是 3.4025 秒。程式碼依然簡潔易懂。一個小缺點是您需要創建一個向量來追蹤非素數（也就是說，您不能透過連接來增加列表 - 我們稍後會看到這不一定是一個優勢）。這使得尋找n 個質數的問題變得更加困難，因為您不知道到底需要多大的向量。
以下是兩個優化版本。第一步先刪除所有 2 的倍數，然後只循環遍歷從 3 開始的奇數。 Sqrt( n ) 用於外循環的上限，因為所有小於該值的非質數都已被篩選。例如，要找出所有小於 100 的質數，您只需篩選到 10。這些改進將運行時間縮短了一半以上，降至 1.3545。第二段展示了使用 JSL 的矩陣運算進行內循環的優勢，1,000,000 的時間為 0.01625，100,000,000 的時間為 2.6694，提高了近 100 倍！
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
你能做得更好嗎？從理論上講， Atkin 篩選法效率更高，並且已在素數 Atkins 例.JSL和Primes Atkins（優化）.JSL中實現。第一個給出了非最佳化且更容易理解的實現（1,000,000 需要 2.236 秒）。比非最佳化版本的 Eratosthenes 更好。然而，優化版本無法擊敗優化後的埃拉托色尼 (100,000,000 耗時 4.914 秒)。此外，從程序和理論角度來看，它更長、更複雜。
那麼從數字表中讀取呢？雖然這不符合編寫演算法的精神，但我並不是說你不能這樣做。 @Craige_Hales提供了使用此方法的解決方案。鑑於問題規範n不超過 1e8，包含壓縮值的腳本大小需要超過 400 萬個字元的程式碼、4.6MB 的磁碟空間和大約 5.5 秒的載入時間，無論n的大小如何。比其他解決方案慢。雖然 Craige 的腳本既不是最快也不是最短的，但我還是選擇了他，因為他對這個問題採取了獨特的方法，使用了壓縮和並行分配。
尋找n 個質數是一個更具挑戰性的問題。假設您使用篩選器，您將需要建立一個包含最多n個質數的值的向量。為此，需要估計該值的上限。應避免低估，因為這可能需要重新運行部分或全部演算法來找到未篩選的值。 nth prime.jmp 的估計值顯示 6 個不同的估計值。 EST1給出了當n較小時值被低估的情況。許多估計僅適用於n大於特定值的情況，在這些情況下需要小心提供替代估計。 雌二醇2對n ≥ 13 很有效，而東3對更大的值進行了改進。不幸的是，好的界線很少是簡單的。 Est4用於Primes 快速提交.jsl 。雖然它做得不是很好並且低估了n的非常大的值，但它簡單且易於記憶。 這是5是利用非線性方法根據實際值得出的。 Est6透過稍微擾動值來改進這是5 ，以便表中的任何值都不會被低估。不能保證 100 和 1e8 之間不存在低估。表格中的其他欄位給出了每種技術的低估/高估情況。
確定質數可以遵循與生成素數類似的路徑。給定一個數字x ，你可以讓i = 2 。繼續，直到Mod( n , i ) == 0或i == n 。下面的程式碼的好處在於，在i = 2 的初始測試之後只檢查奇數i ，並在i > = Ceiling(Sqrt( n ))時停止。
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
上述腳本大約需要 1.4 秒來檢查表大數表.jmp ( 小的 ) 中的所有 1,000 個八位和九位數字。
為了進一步改進這一點，您可以產生一個質數向量（最多為Ceiling(Sqrt( n )) ）並對其進行迭代。
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
這將時間縮短了一半以上，降至 0.6 秒以下。
提高速度的兩個一般注意事項：在需要多次使用矩陣值的情況下，使用變數而不是索引矩陣將該值指派給變數會更快。雖然這可能會使程式碼更長，但它可以節省時間。嘗試透過用其索引矩陣值（ 入參[i] ）替換上述程式碼中的下一個值來做到這一點。其次，隨著矩陣規模的增加， 地方和矩陣連接的速度會變慢。如果您可以使用排序矩陣， 位置排序會執行二進位搜索，並且速度更快。有關矩陣引用和連接的更多範例，請參閱速度測試矩陣操作.jsl 。
試著在大數（ 大的 ）欄位中尋找質數是比較困難的。找到前 10 個大約需要 1.9 秒。此時，你必須依靠專門的演算法來提供改進。 米勒-拉賓（MR）是一種常用且相對容易實現的質數檢定技術。 millerRabin1.jsl中給出了確定性版本。 MR 依賴模冪運算，必須小心謹慎，以免引發溢位錯誤。 MR 本身需要 5.28 秒才能處理完所有 1000 個大數字。你可能會驚訝於 MR 在處理小數時比上面第一個 isPrime 演算法（2.34 秒）慢。這可能是因為隨著數字的增加，它的計算效率會更高，這表明了一種改進方法：使用上面的 2) 測試一定大小的素數。如果該數字是質數，則停止。否則，切換到 MR。此方法可以在millerRabin2.jsl中找到。進行了一些調整來找到要檢查的理想質數。這將時間縮短了一半，降至 2.33 秒。
