题目描述

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式
一个整数N。

输出格式
N! 分解质因数后的结果，共若干行，每行一对pi,ci，表示含有pcii项。按照pi从小到大的顺序输出。

数据范围
1≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=23∗3∗5

算法1

使用质数筛得到 范围内的质数
然后看看 每个质数在题目中给与的数字 存在的倍数

考虑到其他同学的竞猜题解 珠玉在前。这里就只做记录 不再贴上自己的理解了(理解一样 表述的可能还没有这片题解好)
精彩题解
题解链接

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    init(n);

    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        int s = 0;
        for (int j = n; j; j /= p) s += j / p;
        printf("%d %d\n", p, s);
    }

    return 0;
}

我的leetcode视频题解空间