欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣LeetCode 204. 计数质数

程序员文章站 2022-03-06 08:21:59
...

力扣LeetCode 204. 计数质数
用一个vector记录出现过所有质数,因为一个数字可以被分为很多个质数相乘,所以记录一个数字是不是质数,只要看它能不能被其它质数整除,所以只要用1——n的数字去除以 vector中的质数,只要能被其中一个质数整除就说明不是质数,转到下一个数字,如果除以所有vector中质数后都不能被除尽,说明为质数,将其放入vector中。

class Solution {
public:
    int countPrimes(int n) {
        
        if(n<=2){//排除特殊情况
            return 0;
        }
        vector<int>arr;//记录所有的质数
        arr.push_back(2);//当n大于等于3的时候必定有一个质数为2
        for(int i=3;i<n;i++){
            bool sig=true;//设置flag,如果变为false说明该数字不为质数
            for(int j=0;arr[j]<=sqrt(i);j++){
                if(i%arr[j]==0){ 
                    sig=false;
                    break;
                }
            }
            if(sig){
                arr.push_back(i);
            }        
        }
        return arr.size();
    }
};
相关标签: 力扣题目