未分類

Count Primes

Go, HashTable, LeetCode, Math

Count Primes

Count the number of prime numbers less than a non-negative number, n.

提示 解題應用
HashTable Array
Math 規律觀查

Default:

1
2
3
func countPrimes(n int) int {
}

解答思路:

非常典型的空間換取時間，因為在最初一開始我是將2~n的數字每個去除2~√n如果餘數為0就表示非質數，不從1開始是因為1不是質數，除數為1也沒有意義，至於為什麼不是除數除到n而是根號n，可以去參考leetcode本題的提示有解說原理，以前寫類似的題目是直接除數除到n/2要再快些才√n，而以go來說出來的結果要上約1500ms，超時沒辦法通過，就算為了避免呼叫到開根號的函式而將其判斷式平方(j<=√n)[j^2<=n]也只約1400ms一樣沒辦法，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var count int
flag := true
for i := 2; i < n; i++ {
	for j := 2; j*j <= i; j++ {
		if i%j == 0 {
			flag = false
			break
		}
	}
	if flag {
		count++
	}
	flag = true
}
return count

即然不需要擔心空間上的問題就只好以空間來換取時間，將2~n所有是否為質數的狀態全部儲存下來，之後每發現一個質數，就再利用迴圈將其所有倍數的狀態給相反直到n，而最後保留下來狀態沒被改變的就是我們要的結果，可以一邊做計算或是選擇最後再遍歷全部的狀態來計算，此方式甚至連1ms都不到，但是會花費大量的空間。

程式碼解說:

一開始要宣告與n相同長度的陣列，用來儲存2~n所有是否為質數的狀態，不過在儲存時因為是index，所以要記得-1，之後就開始以迴圈一個個找出質數，正因為開頭的2、3…皆為質數，所以一開始再以另一個迴圈篩選所有其倍數時就已經除去大部分非質數的結果了，此時便可以安心的一邊做計算數量，一邊繼續找質數並篩選其倍數，最後就可以將總數做回傳

1
2
3
4
5
6
7
8
9
10
11
var count int
notPrime := make([]bool, n)
for i := 2; i < n; i++ {
	if !notPrime[i-1] {
		count++
		for j := 2; i*j < n; j++ {
			notPrime[i*j-1] = true
		}
	}
}
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
func countPrimes(n int) int {
	var count int
	notPrime := make([]bool, n)
	for i := 2; i < n; i++ {
		if !notPrime[i-1] {
			count++
			for j := 2; i*j < n; j++ {
				notPrime[i*j-1] = true
			}
		}
	}
	return count
}

總結:

如果在做質數上的判斷超時，建議以空間來換取時間，將2~n所有是否為質數的狀態全部儲存下來，之後每發現一個質數，就再利用迴圈將其所有倍數的狀態給相反直到n，而最後保留下來狀態沒被改變的就是結果。

分享到