[LeetCode] 204. Count Primes

轉自LeetCode

Description:

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

<Solution>

這邊有個解題的影片 https://www.youtube.com/watch?v=eKp56OLhoQs

主要想法如下

• 先從 2 這個質數開始，然後把所有小於 n 的 2 的倍數，都標記起來不計算

• 一個加速的方式是，只有小於等於 sqrt(n) 的質數，才需要去把該質數的倍數都去劃掉(詳細解釋可看影片)

code 如下

Java

	class Solution {
	public int countPrimes(int n) {
	if (n == 0) {
	return 0;
	}
	boolean[] notPrime = new boolean[n];
	int cnt = 0;
	final int limit = (int)Math.sqrt(n);
	for(int i = 2; i < n; ++i) {
	if(!notPrime[i]) {
	++cnt;
	if (i <= limit) {
	for(int j = 2; j * i < n; ++j) {
	notPrime[i*j] = true;
	}
	}
	}
	}
	return cnt;
	}
	}

view raw countPrimes.java hosted with ❤ by GitHub

C++

	class Solution {
	public:
	int countPrimes(int n) {
	if (n == 0) {
	return 0;
	}
	bool notPrime[n] = {false};
	int cnt = 0;
	const int limit = sqrt(n);
	for(int i = 2; i < n; ++i) {
	if (!notPrime[i]) {
	++cnt;
	if(i <= limit) {
	for (int j = 2; j * i < n; ++j) {
	notPrime[j * i] = true;
	}
	}
	}
	}
	return cnt;
	}
	};

view raw countPrimes.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun countPrimes(n: Int): Int {
	if (n == 0) {
	return 0
	}
	val notPrime = BooleanArray(n) {false}
	notPrime[0] = true
	val limit = Math.sqrt(n.toDouble())
	var ans = 0
	for(i in 2 until n) {
	if(!notPrime[i]) {
	++ans
	if (i <= limit) {
	var j = 2
	while(i*j < n) {
	notPrime[i*j] = true
	++j
	}
	}
	}
	}
	return ans
	}
	}

view raw count_primes.kt hosted with ❤ by GitHub