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

小于N的素数个数

程序员文章站 2024-03-14 21:12:59
...
class Solution {
public:
    /**
     * 计算小于N的素数的个数。
     * @param n int整型 
     * @return int整型
     */
    int countPrimes(int n) {
        // write code here
        vector<int> vec;
        vec.push_back(2);
        vec.push_back(3);
        vec.push_back(5);
        vec.push_back(7);
        vec.push_back(11);
        if(n == 0 || n == 1){
            return 0;
        } else if(n <= 11) {
            int i = 0;
            for(int j = 0 ; j < vec.size(); j++) {
                if(vec[j] < n) {
                    i++;
                } else {
                    break;
                }
            }
            return i;
        }
        bool flag = true;

        for(int k = 12; k < n ; k++) {
            flag = true;
            for (int i = 0; i < vec.size(); i++) {
                if( vec[i] * vec[i] > k ) {
                    break;
                }
                if(k % vec[i] == 0 ) {
                    flag = false;
                    break;
                }
            }

            if(flag) {
                vec.push_back(k);
            }
        }
        return vec.size();
    }
};