AcWing 197. 阶乘分解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 197. 阶乘分解原题链接中等

作者：

Object_ , 2019-10-01 10:24:28 , 所有人可见 , 阅读 7785

69

22

算法原理：

（文章链接）

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e6;
int primes[MAXN],primeCnt=0;
bool notPrime[2*MAXN];
void initPrime(int x){
    for(int i=2;i<=x;i++){
        if(notPrime[i])continue;
        for(int j=2;j<=x/i;j++){
            notPrime[i*j]=1;
        }
    }
    for(int i=2;i<=x;i++)
        if(!notPrime[i])primes[++primeCnt]=i;
}
int ans[MAXN],ansValue[MAXN];
int main(){
    int n;
    scanf("%d",&n);
    initPrime(n);
    for(int i=1;i<=primeCnt;i++){
        int tmpN=n,nowPrime=primes[i],nowAns=0;
        while(tmpN){
            nowAns+=(tmpN/nowPrime);
            tmpN/=nowPrime;
        }
        printf("%d %d\n",nowPrime,nowAns);
    }
    return 0;
}