阶乘分解质因数

 n!中因子p的个数为

枚举n范围内的质数即可

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;
 
const int N = 1000010;
 
int n;
int primes[N], cnt;
bool st[N];
 
void init()
{
	for(int i = 2; i <= n; i ++)
	{
		if(!st[i])
		{
			primes[cnt ++] = i;
		}
		for(int j = 0; primes[j] * i <= n; j ++)
		{
			st[primes[j] * i] = true;
			if(i % primes[j] == 0)break;
		}
	}
}
 
int main()
{
	IOS
	cin >> n;
	init();
	for(int i = 0; i < cnt; i ++)
	{
	    int p = primes[i];
	    int res = 0, x = n;
	    while(x)
	    {
	        res += x / p;
	        x /= p;
	    }
	    cout << primes[i] << ' ' << res << endl;
	}
	
	return 0;
}