分解质因数

参考资料

• 分解质因数 - OI Wiki

朴素算法

枚举 $2$ 到 $\sqrt n$ 的整数，逐个把因子从 $n$ 中除尽，剩余大于 $1$ 的部分是最后一个质因子。时间复杂度为 $O(\sqrt n)$。

135 Bcpp

void factorize(ll n)
{
	int cnt=0;
	for(ll k=2;k*k<=n;k++)
	{
		while(n%k==0)
		{
			a[++cnt]=k;
			n/=k;
		}
	}
	if(n!=1)a[++cnt]=n;
}

Pollard Rho 算法

Pollard Rho 用于快速分解大整数。它构造伪随机序列 $x_{i+1}=x_i^2+c\bmod n$，由生日悖论，期望 $O(n^{1/4})$ 步内能找到两个对 $n$ 的某质因子同余的数，二者之差与 $n$ 的 $\gcd$ 即为一个非平凡因子。配合 Miller–Rabin 判素后递归分解。下面的实现用倍增与批量求积（每 $127$ 步取一次 $\gcd$）优化常数。

1.28 KBcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using ld=long double;
ll mul(ll a,ll b,ll mod)
{
	return (a*b-ll(ld(a)/mod*b+0.5)*mod+mod)%mod;
}
ll Pow(ll x,ll y,ll mod)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=mul(res,x,mod);
		x=mul(x,x,mod);
		y>>=1;
	}
	return res;
}
bool miller_rabin(ll n,int k)
{
	if(n<2)return 0;
	if(n==2||n==3)return 1;
	ll d=n-1,r=0;
	while(!(d&1)){r++;d>>=1;}
	while(k--)
	{
		ll x=Pow(rand()%(n-2)+2,d,n);
		if(x==1||x==n-1)continue;
		for(int i=0;i<r-1;i++)
		{
			x=mul(x,x,n);
			if(x==n-1)break;
		}
		if(x!=n-1)return 0;
	}
	return 1;
}
ll pollard_rho(ll n)
{
	ll c=rand()%(n-1)+1,sum=0,tmp=0;
	for(int i=1;;i*=2)
	{
		ll val=1;
		for(int j=1;j<=i;j++)
		{
			sum=(mul(sum,sum,n)+c)%n;
			val=mul(val,abs(sum-tmp),n);
			if(j%127==0)
			{
				ll g=__gcd(val,n);
				if(g>1)return g;
			}
		}
		ll g=__gcd(val,n);
		if(g>1)return g;
		tmp=sum;
	}
}
ll ans;
void factorize(ll n)
{
	if(n<2||n<=ans)return;
	if(miller_rabin(n,10)){ans=max(ans,n);return;}
	ll p=n;
	while(p>=n)p=pollard_rho(n);
	while(n%p==0)n/=p;
	factorize(n);
	factorize(p);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll n;
		cin>>n;
		ans=0;
		factorize(n);
		if(ans==n)cout<<"Prime"<<'\n';
		else cout<<ans<<'\n';
	}
	return 0;
}

例题

洛谷 B3715 分解质因子 2

给定一个正整数 $n$，设 $n=p_1\times p_2\times\dots p_k$，其中 $p_i$ 均为质数，对 $1\leq i<k$，$p_i\leq p_{i+1}$。

可以证明，序列 $p_i$ 是唯一的。

对每个给定的 $n$，请你求出 $p_1, p_2,\dots p_k$。

洛谷 P4718 【模板】Pollard-Rho

对给定的 $T$ 个正整数，分别判断是否为质数：是质数输出 Prime，否则输出其最大质因子。