网站设计的思路,最差网站设计,电子商务电商网站设计,网站备案 互联网信息查询#中等#枚举 给定整数 n #xff0c;返回 所有小于非负整数 n 的质数的数量 。 埃氏筛 枚举没有考虑到数与数的关联性#xff0c;因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法#xff0c;该算法由希腊数学家厄拉多塞#xff08;Eratosthenes#xff09;提…#中等#枚举
给定整数 n 返回 所有小于非负整数 n 的质数的数量 。 埃氏筛 枚举没有考虑到数与数的关联性因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法该算法由希腊数学家厄拉多塞Eratosthenes提出称为厄拉多塞筛法简称埃氏筛。 我们考虑这样一个事实如果 x 是质数那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数因此我们可以从这里入手。 我们设 isPrime[i] 表示数 i 是不是质数如果是质数则为 1否则为 0。从小到大遍历每个数如果这个数为质数则将其所有的倍数都标记为合数除了该质数本身即 0这样在运行结束的时候我们即能知道质数的个数。 这种方法的正确性是比较显然的这种方法显然不会将质数标记成合数另一方面当从小到大遍历到数 x 时倘若它是合数则它一定是某个小于 x 的质数 y 的整数倍故根据此方法的步骤我们在遍历到 y 时就一定会在此时将 x 标记为 isPrime[x]0。因此这种方法也不会将合数标记为质数。 当然这里还可以继续优化对于一个质数 x如果按上文说的我们从 2x 开始标记其实是冗余的应该直接从 x⋅x 开始标记因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了例如 2 的所有倍数3 的所有倍数等。 官方题解 class Solution {
public:int countPrimes(int n) {vectorint isPrime(n, 1);int ans 0;for (int i 2; i n; i) {if (isPrime[i]) {ans 1;if ((long long)i * i n) {for (int j i * i; j n; j i) {isPrime[j] 0;}}}}return ans;}
};//官方题解 class Solution {
public:int countPrimes(int n) {vectorint primes;vectorint isPrime(n, 1);for (int i 2; i n; i) {if (isPrime[i]) {primes.push_back(i);}for (int j 0; j primes.size() i * primes[j] n; j) {isPrime[i * primes[j]] 0;if (i % primes[j] 0) {break;}}}return primes.size();}
};作者力扣官方题解
链接https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
class Solution {
public:int countPrimes(int n) {vectorintisPrime(n,1);//线性筛vectorintprime;for(int i2;in;i){if(isPrime[i]){prime.push_back(i);}for(int j0;jprime.size()prime[j]*in;j){isPrime[prime[j]*i]0;if(i%prime[j]0)break;}}return prime.size();}
};
