本篇為LeetCode上演算法的簡單問題,Count Primes 數質數。
題目如下:
Count the number of prime numbers less than a non-negative number, n.
Example:
Input:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
輸入一正整數n,計算小於n的整數中有多少個質數(prime)。
所謂的質數是指大於1且只能被1和自己整除的整數。而依照此定義想到的解法如下。
public static int countPrimes3(int n) {
if(n < 2) { // 負數,0,1不考慮
return 0;
}
n = n - 1; // 只算小於n的質數
int primeCount = 0; // 質數計數
for (int i = 2; i < n; i++) { // 被除數,從2開始
int divisibleCount = 0; // 被整除的次數
for (int j = 2; j < n; j++) { // 除數,從2開始
if (i % j == 0) { // 被除數除以除數餘數若為0
divisibleCount++; // 被整除的次數 + 1
}
}
if(divisibleCount == 1) { // 當被整除的次數只有1次,代表目前的被除數只能被自己整除
primeCount++; // 質數計數 + 1
}
}
return primeCount;
}
但效率極差,根本無法通過LeetCode的時間限制,因為時間複雜度為O(N2),當N = 10,000時,代表直行次數為100,000,000(1億)次。
參考別人的答案如下
public static int countPrimes(int n) {
if(n < 3) {
return 0;
}
int primeCount = 0;
boolean[] nonPrimes = new boolean[n]; // 用來記錄非質數的陣列
for (int i = 2; i < n; i++) {
if(nonPrimes[i]) { // 整數i是否為質數?若是則跳過
continue;
}
primeCount++; // 若不是質數次數 + 1
for (long j = (long)i * i; j < n; j += i) { // 整數i自乘的數必為非質數,且自乘數i2 + i*n也仍為非質數
nonPrimes[(int) j] = true;
}
}
return primeCount;
}
在上面的內迴圈中,從2開始自乘取得每個非質數並放入記錄非質數的陣列中,
當i=2時,分別得到4, 6, 8, 10, ... , n - 2;
當i=3時,分別得到9, 12, 15, 18, ... , n - 3;
...
而在外迴圈又會先判斷非質數陣列中某整數i是否存在,若存在代表i為非質數,則不繼續執行內迴圈。
改善一下,只要是2的倍數都是非質數,所以直接略過不考慮,如此內迴圈的執行次數至少就減少了一半。
public static int countPrimes(int n) {
if (n < 3) {
return 0;
}
int count = 1; // 先算入整數2
boolean[] nonPrimes = new boolean[n];
for (int i = 3; i < n; i += 2) { // 不考慮2的倍數
if (nonPrimes[i]) {
continue;
}
count++;
for (long j = (long) i * i; j < n; j += i) {
nonPrimes[(int) j] = true;
}
}
return count;
}
更快的寫法如下。
public static int countPrimes6(int n) {
if (n < 3) {
return 0;
}
int count = n / 2;
boolean[] nonPrimes = new boolean[n];
for (int i = 3; i * i < n; i += 2) {
if (nonPrimes[i]) {
continue;
}
for (long j = (long) i * i; j < n; j += 2 * i) {
if (!nonPrimes[(int) j]) {
--count;
nonPrimes[(int) j] = true;
}
}
}
return count;
}
沒有留言:
張貼留言