在計算機科學中,素數是指只能被1和本身整除的自然數。如2、3、5、7、11等都是素數,而4、6、8等都不是素數。在這篇文章中,我們將探討使用JavaScript函數來判斷一個數是否是素數。
要判斷一個數是否是素數,最直觀的方法就是將這個數從2開始,一直到該數的平方根的所有數中,分別進行取余運算。如果有任意一個數可以整除這個數字,那么它就不是素數。
function isPrime(num) { //判斷數字是否大于1 if (num<= 1) { return false; } //從2開始,一直到該數的平方根的所有數中,分別進行取余運算 for (let i = 2; i<= Math.sqrt(num); i++) { if (num % i === 0) { return false; } } return true; } //測試示例 console.log(isPrime(2)); //true console.log(isPrime(10)); //false console.log(isPrime(17)); //true
在上面的代碼中,我們首先判斷數字是否大于1,因為任何小于或等于1的數字都不是素數。接著我們循環從2到該數的平方根的所有數,分別進行取余運算,如果這個數字可以被其中任意一個數整除,則表明它不是素數,返回false。如果上面的循環中沒有找到可以整除的數字,那么就表明當前數字是素數,返回true。
這個函數的時間復雜度是O(√n)。因為在最壞情況下,要循環到該數的平方根才能確定是否為素數。比如,對于數字15,我們需要循環到3才能確定它不是素數。對于如此巨大的數字,這個函數耗時可能比較長。
有一個額外的方法來加速這個函數——埃拉托色尼篩法。它會提前判斷n以內的所有素數,讓后一個測試的數字只對已知的素數進行取余操作。
function sieveOfEratosthenes(max) { let sieve = []; let primes = []; for (let i = 2; i<= max; ++i) { if (!sieve[i]) { primes.push(i); for (let j = i<< 1; j<= max; j += i) { sieve[j] = true; } } } return primes; } function isPrime(num) { if (num<= 1) { return false; } let primes = sieveOfEratosthenes(Math.sqrt(num)); for (let i = 0; i< primes.length; i++) { if (num % primes[i] === 0) { return false; } } return true; } //測試示例 console.log(isPrime(2)); //true console.log(isPrime(10)); //false console.log(isPrime(17)); //true
在上面的代碼中,我們首先使用埃拉托色尼篩法生成了小于等于n的所有素數。接著我們循環這些素數,進行取余操作,判斷當前數字是否是素數。如此一來,我們就不需要循環到該數的平方根了。
JavaScript函數可以很方便地判斷一個數是否是素數。無論是使用最直觀的方法,還是使用埃拉托色尼篩法,我們能夠快速而準確地判斷任意數字是否為素數。在計算機科學中,素數的判定是一個重要的問題,使用這些函數可以使我們的代碼更高效、更可靠。