Leetcode Answers 204

今天继续刷题,边刷边看面经和CC150。先是一道开胃的Easy题,查质数的个数。

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

思路:
简单明了的一句话问题。质数的定义就不说了,这里要说的是Sieve of Eratosthenes,一个我不知道怎么翻译但是我知道大概是要干什么的方法,就是在给定的范围内,从2开始,先乘方,再从乘方开始找这个数字的倍数,并全部标记为非素数,这样找下去等到所有的小于给定范围的平方根的数字都找完了,剩余的未标记的就都是质数了。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int CountPrimes(int n) {
if(n < 2) return 0;
var isPrime = new bool[n];
for(int i = 0; i < n; ++i) isPrime[i] = true;
for(int i = 2; i * i < n; ++i){
if(isPrime[i]){
for(int j = i * i; j < n; j += i){
isPrime[j] = false;
}
}
}
int count = 0;
for(int i = 2; i < n; i++){
if(isPrime[i]) ++count;
}
return count;
}
}

没什么可考察的,简单易懂。

以上。

17-04-25
@Sturbridge