跳转至

204 计数质数

什么是质数

质数是除了1和自己以外,不能被其他数整除的数

特别地,1不是质数,质数要求大于1

例如:

  • 5 = 1 * 5,5是质数
  • 6 = 1 * 6, 6 = 2 * 3,6能被2和3整除,6不是质数
如何判断质数

假设我们想知道x是不是质数,那么需要遍历所有比x小的自然数i(从2开始),如果存在x % i == 0说明存在不为1和自身的自然数,能被x整除,因此x不满足质数定义

如果遍历结束,都没有找到这么一个i,那么x就是质数

leetcode

思路讲解

链接讲的非常清楚,我就不赘述了

class Solution {
public:
    // 判断质数
    bool isPrime(int k){
        for(int i = 2; i < k; i++){
            if(k % i == 0)
                return false;
        }
        return true;
    }
    int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime(i))
                count++;
        }
        return count;
    }
};

可以进一步优化:

判断是否是质数时,不需要遍历所有小于x的元素,而是遍历小于sqrt(x)的元素

class Solution {
public:
    // 判断质数
    bool isPrime(int k){
        // 在这里优化: i < k => i * i <= k
        for(int i = 2; i * i <= k; i++){
            if(k % i == 0)
                return false;
        }
        return true;
    }
    int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime(i))
                count++;
        }
        return count;
    }
};
class Solution {
public:
    int countPrimes(int n) {
        // 因为素数筛选法判断的是「不是质数的数」,因此默认都是质数
        vector<bool> isPrime(n + 1, true);
        for(int i = 2; i < n; i++){
            // 如果是质数,则根据该质数排除一系列不是质数的数
            if(isPrime[i]){
                // 从2 * i开始,3 * i, 4 * i等等都不是质数
                for(int j = 2 * i; j < n; j += i){
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                count++;
            }
        }
        return count;
    }
};

可以进一步优化:

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> isPrime(n + 1, true);
        // *优化1
        // 由对称性可知,判断质数不需要遍历所有小于n的i
        // 只需要遍历[2, sqrt(n)]
        for(int i = 2; i * i < n; i++){
            if(isPrime[i]){
                // *优化2
                // 避免例如2 * 5 和 5 * 2的重复,j从i * i开始
                for(int j = 2 * i; j < n; j += i){
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                count++;
            }
        }
        return count;
    }
};