leetcode 204： Count Primes

2023-10-14 02:58

文章标签 leetcode count primes 204

本文主要是介绍leetcode 204： Count Primes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

Description:

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

思路：

首先我想到的思路是暴力遍历检测，然后计数，所以写了一个判断是否为质数的函数ifPrime，然后遍历所有小于n的奇数判断是否质数并计数。而ifPrime函数判断某数k是否质数的实现，是用小于k^1/2的所有奇数去除k，若存在能整除就不是质数。如代码一。

但是提交后不意外地Time Limit Exceeded了。于是找了下判断质数的方法，找到一个比较符合计数过程并且稍为简单的埃拉托斯特尼筛法Sieve of Eratosthenes。该算法思想是，建立一个很大的数组，然后没找到一个质数，就把该质数的倍数都删除（标记不可能为质数），然后下一次遍历到第一个可能为质数的数字就是质数。实现如代码二。

代码：

代码一：

class Solution {
public:int countPrimes(int n) {if (0 == n || n == 1) return 0;if (n == 2) return 1;if (n == 3) return 2;int count = 1;for (int i = 3; i < n; i+=2){if (isPrime(i)) count++;}return count;}//determine if it is primebool isPrime(int n){if (1 == n) return false;if (2 == n || 3 == n || 5 == n) return true;if (n % 2 == 0) return false;for (int i = 3; i <= sqrt(n); i+=2){if (n % i == 0) return false;}return true;}
};

代码二：

class Solution {
public:int countPrimes(int n) {if (0 == n || 1 == n) return 0;bool *p = new bool[n];for (int i = 2; i < n; i++){p[i] = false;}int count = 0;int last_prime = 1; while (1){for (int i = last_prime + 1; i < n; i++)   //遍历前一个质数后的数{if (p[i] == false)  //找到第一个，就是新质数{count++;last_prime = i;//将i倍数都置为非质数for (; i < n; i += last_prime){p[i] = true;}break;}//for循环遍历到租后一个下标也没有也没进入"p[i] == false"的条件语句，就说明遍历完毕均为trueif (i == n - 1) return count;  }//上一个prime number是n-1时，无法进入for循环，需要这里判断一下并returnif (last_prime == n - 1) return count;}}
};