敢問施主
使用何種程式語言
若不知語言名稱
只得下圖相贈
這樣算嗎?
const primes = [
19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
397
];
for(let i=0; i<primes.length; ++i) {
console.log(primes[i]);
}
這題目很弔詭
因為如果只是問「18~399」間的質數,那真的沒什麼學問
但如果希望做一個「可以計算任意M~N間質數」的方法然後又希望兼顧演算效率
那就是學問了
幾個秘訣
1.首先判斷是否為偶數,如果是就別浪費力氣去計算了,如果傳入的M是偶數,則將它+1。然後回圈至少以+2遞增做運算。
2.承1。因為已經排除所有偶數了,做因數檢查時可以跳過2。
3.承2。因為已經排除所有偶數了,做因數檢查時可以從3開始做+2遞增。
4.絕大多數的演算法在做因數檢查時,都會直接檢查到X-1,(X是回圈目前跑到的數值,)這其實毫無必要毫無道理,因為任何數X都不會有大於X/2的因數。
5. (以下不明,可以自己自由發揮,我個人只有以上四個秘訣。)
質數判斷是數學數論的終極題目之一
用計算機跑迴圈是暴力硬破解
但不是什麼東西都可以暴力硬破解的
質數:只能用1或本身除盡的數
所有的數都可以=用質數來相乘
所以要定義一個空陣列PN來儲存質數(初始值1,2)
再用雙迴圈處理(語法自己去套)
define array PN=(1,2);
for N =(18..399) {
ispn=0;
for (i=0;i<=(PN數量);i++) {
if N/PN[i]取餘數==0 { ispn++ } #整除
if ispn>2 { exit for } #
}
if ispn=2 { push PN,N } #質數丟入陣列PN
}
最後印出PN即可
其實:N=1或自己可以不用算,程式更有效率
這個問題很難,我花了好幾天的下班時間,終於完成
更新質數表([], X, [X]).
更新質數表([H|T], X, [H|L]):-
更新質數表(T,X,L).
非質數([X | _], Value):-
Mod is Value mod X,
Mod = 0.
非質數([_ | Other], Value):-
非質數(Other, Value).
質數(Primes, From, To):-
From > To,
write(Primes).
質數(Primes, From, To):-
非質數(Primes, From),
Next is From + 1,
質數(Primes, Next, To).
質數(Primes, From, To):-
更新質數表(Primes, From, New),
Next is From + 1,
質數(New, Next, To).
main:-
質數([2, 3, 5, 7, 11, 13, 17], 18, 399),
halt.