蓝桥集训之阶乘分解

• 核心思想：线性筛质数

  • 

    • 筛出每一个质数后 只要将所有质数的1 2 3 … 次方个数都加上即可

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    const int N = 1e6+10;
    int prime[N],cnt;
    int n;
    bool st[N];
    
    void get_primes(int n)
    {
        for(int i=2;i<=n;i++)
        {
            if(!st[i]) prime[cnt++] = i;  //没有被筛 是质数 记录下来
            for(int j=0;prime[j]*i<=n;j++)  //遍历所有质数 筛掉其倍数
            {
                st[prime[j]*i] = true;  //prime[j]*i保证在n以内
                if(i%prime[j] == 0) break;  //如果i是prime[j]倍数 说明prime[j]为i最小因数
            }
        }
    }
    
    int main()
    {
        cin>>n;
        get_primes(n);
        for(int i=0;i<cnt;i++)
        {
            int p = prime[i];
            int s = 0,t = n;
            while(t) s+=t/p , t/=p;   //t可能是p的平方 要加两次
            cout<<p<<" "<<s<<endl;
        }
        return 0;
    }