素数筛C++

向右看齐 2022-02-09 11:15 299阅读 0赞

**埃拉托斯特尼筛法（sieve of Eratosthenes ）** 是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素数p1到pk，其中k = sqrt(n)，依次剔除Pi的倍数，剩下的所有数都是素数。  
具体操作如上述 图片所示。

## C++实现 ##

#include<iostream>
    #include<vector>
    using namespace std;
     
    int main(){
        
        int n;
        cin>>n;
        vector<bool> isprime(n+5, true);
        vector<int> ans;
        for(int i = 2; i <= n; i++){
        
            if(isprime[i]){
        
                ans.push_back(i);
                for(int j = i * i; j <= n; j += i)isprime[j] = false;
            }
        }
        for(auto i : ans)cout<<i<<" ";
        cout<<endl;
        return 0;
    }

## 整除问题 ##

给定n，a求最大的k，使n！可以被a^k  
整除但不能被a^(k+1)整除。

#include<iostream>
    #include<vector>
    #include<map>
    using namespace std;
     
    int main(){
        
        int n, a, temp;
        int ans = 0x7fffffff;
        cin>>n>>a;
        vector<bool> isprime(1010, true);
        vector<int> prime;  //素数列表
        map<int, int> primecntnp;  //存储n!的质因子的指数
        map<int, int> primecnta;  //存储a的质因子的指数
        for(int i = 2; i <= 1010; i++){
          //采用素数筛选出前1010个数中的素数，并将map初始化
            if(isprime[i]){
        
                prime.push_back(i);
                primecntnp[i] = primecnta[i] = 0;
                for(int j = i*i; j<= 1010; j += i)isprime[j] = false;
            }
        }
        //4! = 24 = 1*2*3*4 = 2*2*2*3
        for(int i = 0; i < prime.size(); i++){
         //对n!进行因式分解
            temp = n;
            while(temp){
         //按照p、p*p、p*p*p来进行因式分解
                primecntnp[prime[i]] += temp/prime[i];
                temp /= prime[i];
            }
        }
        for(int i = 0; i < prime.size(); i++){
         //对a进行因式分解
            temp = a;
            while(temp % prime[i] == 0){
        
                primecnta[prime[i]]++;
                temp /= prime[i];
            }
            if(primecnta[prime[i]] == 0)continue; //a里面不存在的则无法提供
            if(primecntnp[prime[i]]/primecnta[prime[i]] < ans)ans = primecntnp[prime[i]]/primecnta[prime[i]];
        }//找到最小的指数，便是最大的k值
        cout<<ans<<endl;
        return 0;
     }
     /*
    555 12
    274
     */

[omegaxyz.com]: http://xn--omegaxyz-on6m893d6sgwn0bu73h213a.com