CH 3101 阶乘分解（算法竞赛进阶指南，阶乘的素因子分解）

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int MaxN = 1000010;
    int prime[MaxN], v[MaxN];
    long long n; 
    int	pNum;
    int fac[MaxN];
    long long fac_cnt[MaxN];
    
    void prime_init()	//线性筛法求素数
    {
    	pNum = 0;
    	for(int i = 2; i <= n; ++i)
    	{
    		if(!v[i])
    		{
    			v[i] = i, prime[++pNum] = i;
    		}
    		for(int j = 1; j <= pNum; ++j)
    		{
    			if(prime[j] > v[i] || prime[j] > n / i)
    				break;
    			v[i * prime[j]] = prime[j];
    		}
    	}
    }
    
    void solve()
    {
    	int m = 0;
    	for(int i = 1; prime[i] <= n && i <= pNum; ++i)
    	{
    		fac[++m] = prime[i];
    		long long multi = prime[i], count = 0;
    		while(multi <= n)		// 这里比较大小，使用 long long 来比较
    		{
    			count += n / multi;
    			multi *= prime[i];
    		}
    		fac_cnt[m] = count;
    	}
    	for(int i = 1; i <= m; ++i)
    	{
    		printf("%d %lld\n", fac[i], fac_cnt[i]);	
    	}
    }
    
    
    int main()
    {
    	scanf("%lld", &n);
    	prime_init();
    	solve();
    	return 0;
    }
    
    /*
    5
    */
    
    /*
    2 3
    3 1
    5 1
    */