【代码超详解】洛谷 P2043 质因子分解（分解质因数）

一、题目描述

题目描述

对N!进行质因子分解。

输入格式

输入数据仅有一行包含一个正整数N，N<=10000。

输出格式

输出数据包含若干行，每行两个正整数p,a，中间用一个空格隔开。表示N!包含a个质因子p,要求按p的值从小到大输出。

输入输出样例

输入 #1

10

输出 #1

2 8
3 4
5 2
7 1

说明/提示

10!=3628800=(2^8)*(34)*(5^2)*7

二、算法分析说明与代码编写指导

基于分解质因数的模板进行改动，在质因子表中的结果保留而不是在分解下一个数之前清除。先打质数表，然后对 2 到 n 分解质因数。
本代码中，质因子表被拆成了两个 vector F 和 E。F = factor，E = exponent。
试除法只试除到根号 n。剩下的数如果还是质数，也要记录。如果不是质数，意味着待分解的数太大，超出了代码可以分解的范围，分解不完全。不过对本题而言，由于 n ≤ 10000，而且查表知只需要打一张包含前 1229 个质数的质数表就可以覆盖 10000 以内的质数，保证可以分解。
将 n！的质因子存入表后，就可以输出所有次数不是 0 的质因子及其次数了。
（off = offset）

三、AC 代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#pragma warning(disable:4996)
using namespace std;
unsigned prime[1229] = { 2,3 }, _PrimeTy, MaxPrime, * prime_end = prime + sizeof(prime) / sizeof(prime[0]);
inline void gen_prime() {
	decltype(_PrimeTy) a = 4, t; bool flag = true;
	for (auto i = prime + 2; i != prime_end;) {
		t = sqrt(a), flag = true;
		for (auto j = prime; *j <= t; ++j)if (a % *j == 0) { flag = false; break; }
		if (flag) { *i = a, ++i; }
		++a;
	}
	MaxPrime = *(prime_end - 1);
}
inline bool isprime(const decltype(_PrimeTy)& x) {
	if (x <= MaxPrime)return binary_search(prime, prime_end, x);
	else {
		static decltype(_PrimeTy) t; t = min((decltype(_PrimeTy))sqrt(x), MaxPrime);
		for (auto j = prime; *j <= t; ++j)if (x % *j == 0)return false;
		return true;
	}
}
template<class _Ty> inline void pfact(_Ty X, vector<_Ty>& F, vector<_Ty>& E) {//打表的最大质数的平方不能超过X的类型_Ty能够存储的最大值，否则计算出的分解上限L会溢出，导致分解成功与否判断出错。
	static _Ty L = MaxPrime * MaxPrime;
	_Ty t = min((_Ty)sqrt(X), MaxPrime); long long off;
	for (auto d = prime; *d <= t; ++d) {
		if (X % *d == 0) {
			off = d - prime;
			while (X % *d == 0) { X /= *d, ++E[off]; }
		}
		t = min((_Ty)sqrt(X), MaxPrime);
		if (X == 1)return;
	}
	off = lower_bound(prime, prime_end, X) - prime; ++E[off];
}
vector<unsigned> f, e; unsigned n;
int main() {
	scanf("%u", &n); gen_prime();
	for (auto i = prime; *i <= n; ++i) { f.emplace_back(*i); e.emplace_back(0); }
	for (unsigned i = 2; i <= n; ++i)pfact(i, f, e);
	for (size_t i = 0; i < f.size(); ++i) {
		if (e[i] > 0)printf("%u %u\n", f[i], e[i]);
	}
	return 0;
}