註：挑戰條目來自@大衛_伯納姆在截止日期之前提交，但被我的電子郵件系統隔離。 我是在原始部落格文章發表後才發現的。 我正在更新結果以反映基於新條目的變更。
感謝所有為挑戰 2 提交代碼的人。 評分是一項挑戰，因為有些代碼對於較小的值效果更好，而有些代碼對於較大的值效果更好。 下表列出了挑戰各部分的結果。 共有三輪比賽是質數、 1000 個不能被 5 整除的 5 位隨機奇數、不能被 5 整除的 8 位和 9 位奇數、以及不能被 5 整除的 12 至 15 位奇數。 結果基於最後兩個條件。 分數根據挑戰進行分配，1.5 分英石, 1 換 2 ND , 3 時為 0.5 RD 。 也給出了最快提交的時間（以秒為單位）。
@leelaim isPrime(Small) 時間與 JMP 工作人員的速度一樣快 (+3 分)。 @落在isPrime(Big) 腳本使用並行分配函數來提高速度。 其中兩個條目快取了其結果獲取質數使用命名空間。 當需要多次存取結果時，此方法非常有用（但是，運行時間是基於未快取的結果）。 所有這四個條目都包含在下面。
這是兩次挑戰後的排行榜：
挑戰 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 開始的奇數。 平方（ n ) 用於外循環的上限，因為所有小於該上限的非質數都已被篩選出來。 例如，要找出 100 以下的所有質數，只需篩選到 10。 任何大於 10 的質數的篩出數將是該素數乘以小於 10 的數的乘積，該數將與其他素數一起刪除（例如，用 5 的篩子刪除 11*5， 11*9，帶篩子為3等）。 這些改進將運行時間減少了一半以上，達到 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 );
);
你能做得更好嗎？ 這阿特金篩理論上效率更高，並在素數阿特金斯範例.JSL和普林斯阿特金斯（優化）.JSL 。 第一個給出了未優化且更易於理解的實現（1,000,000 需要 2.236 秒）。 比埃拉托色尼的非優化版本更好。 然而，優化版本無法擊敗優化的埃拉托斯特尼（100,000,000 耗時 4.914 秒）。 此外，它在程序上和理論上都更長、更複雜。
從數字表中讀取怎麼樣？ 雖然這不符合寫演算法的精神，但我並沒有說你不能。 @Craige_Hales提供了使用這種方法的解決方案。 給定問題規範n不超過 1e8，包含壓縮值的腳本大小需要超過 400 萬個程式碼字元、4.6MB 磁碟空間和大約 5.5 秒的載入時間，無論大小為何n 。 比其他解決方案慢。 雖然既不是最快的也不是最短的，但我已經包含了 Craige 的腳本，因為他對問題的獨特方法、壓縮的使用以及平行分配。
尋找n素數是一個更具挑戰性的問題。 假設您使用篩子，您需要建立一個值向量，直到n th素數。 為此，需要估計該值的上限。 應避免低估，因為可能需要重新運行部分或全部演算法才能找到未篩選的值。 第 n 個質數的估計值.jmp顯示 6 種不同的估計值。 EST1給出了小值被低估的情況n 。 許多估計僅適用於n大於特定值，在這些情況下需要小心提供替代估計值。 EST2有利於n ≥ 13 且EST3對於更大的值，可以對此進行改進。 不幸的是，好的界線很少是簡單的。 EST4被用於Primes快速提交.jsl 。 雖然它做得不太好並且低估了非常大的值n ，簡單易記。 EST5是使用非線性與實際值得出的。 EST6改進了EST5透過稍微擾動這些值，以便表中的任何值都不會被低估。 不保證 100 到 1e8 之間不存在低估。 其他表列給出了每種技術的低估/高估。
確定質數可以遵循與生成素數類似的路徑。 給定一個數字X ，你可以讓我= 2。 如果模（ n ,我） == 0停止，否則增加我。 繼續直到模（ n ,我) == 0或者我== n 。 下面的程式碼受益於僅檢查奇數我初次測試後我= 2 並且停止時我> = 天花板(平方( 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 秒來檢查表中所有 1,000 個八位和九位數字大數表.jmp (小的）。
為了進一步改進這一點，您可以產生素數向量（最多天花板(平方( 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 秒以下。
提高速度的兩個一般注意事項：在需要多次使用矩陣值的情況下，使用變數而不是索引矩陣將該值指派給變數會更快。 雖然這可能會使程式碼更長，但會節省時間。 透過替換來嘗試這個下一個值在上面的程式碼中及其索引矩陣值（ inVals[i] ）。 第二，洛克且矩陣串聯隨著矩陣大小的增長而變慢。 如果您可以使用排序矩陣，本地排序執行二分搜尋並且速度要快得多。看速度測試矩陣運算.jsl有關矩陣引用和串聯的其他範例。
試著在大數列中找到質數（大的）問題比較多。 找到前 10 個大約需要 1.9 秒。 此時，就必須依靠專門的演算法來進行改進。 米勒-拉賓 (MR)是一種常用且相對容易實現的測試素性的技術。 確定性版本給出米勒拉賓1.jsl 。 MR 依賴模冪運算，必須小心避免產生溢位錯誤。 MR 本身需要 5.28 秒才能完成所有 1000 個任務大的數字。 您可能會感到驚訝，MR 在處理以下問題時比上面的第一個 isPrime 演算法（2.34 秒）慢小的數字。 這可能是因為隨著數字大小的增加，它的計算效率變得更高，這表明了一種改進：使用上面的 2) 測試特定大小的素數。 如果該數字是質數，則停止。 否則，切換到 MR。這種方法可以在米勒拉賓2.jsl 。 進行了一些調整以找到要檢查的理想素數數量。 這將時間縮短了一半，達到 2.33 秒。
