Description:

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

click to show more hints.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

计数出小于非负整数n的质数数量。质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

解法:埃拉托斯特尼筛法 Sieve of Eratosthenes

如果一个数是另一个数的倍数,那这个数肯定不是质数。利用这个性质,可以建立一个质数数组,从2开始将素数的倍数都标注为不是质数。第一轮将4、6、8等表为非质数,然后遍历到3,发现3没有被标记为非质数,则将6、9、12等标记为非质数,一直到N为止,再数一遍质数数组中有多少质数。

[LeetCode] 204. Count Primes 计数质数-LMLPHP

Java:

public class Solution {
public int countPrimes(int n) {
boolean[] prime = new boolean[n];
Arrays.fill(prime, true);
for(int i = 2; i < n; i++){
if(prime[i]){
// 将i的2倍、3倍、4倍...都标记为非素数
for(int j = i * 2; j < n; j = j + i){
prime[j] = false;
}
}
}
int count = 0;
for(int i = 2; i < n; i++){
if(prime[i]) count++;
}
return count;
}
}

Python:

class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
isPrime = [True] * max(n, 2)
isPrime[0], isPrime[1] = False, False
x = 2
while x * x < n:
if isPrime[x]:
p = x * x
while p < n:
isPrime[p] = False
p += x
x += 1
return sum(isPrime)

Python:

class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2: return 0
vis = [False] * n
for i in range(2, int(n ** 0.5) + 1):
if vis[i]: continue
j = i
while j * i < n:
vis[j * i] = True
j += 1
ans = 0
for i in range(2, n):
if not vis[i]: ans += 1
return ans

C++:

class Solution {
public:
int countPrimes(int n) {
if(!n||n==1) return 0;
vector<bool> isPrime(n,true);
// Loop's ending condition is i * i < n instead of i < sqrt(n)
// to avoid repeatedly calling an expensive function sqrt().
for(int i=2;i*i<n;++i)
{
if(!isPrime[i]) continue;
//填表起点i*i,如3*3,因为3*2已填,步长+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;
}
};

  

All LeetCode Questions List 题目汇总

  

05-07 15:56
查看更多