跳到主要内容

分解质因数

参考资料​

朴素算法​

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 算法​

#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​

洛谷 B3715 分解质因子 2

给定一个正整数 nn，设 n=p1×p2×…pkn = p_1 \times p_2 \times \dots p_k，其中 pip_i 均为质数，对 1≤i<k1 \leq i < k，pi≤pi+1p_i \leq p_{i + 1}。

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

对每个给定的 nn，请你求出 p1,p2,…pkp_1, p_2, \dots p_k。

代码（1）
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=105;
ll a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll n;
		cin>>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;
		for(int i=1;i<=cnt;i++)
		{
			cout<<a[i]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

洛谷 P4718 【模板】Pollard-Rho​

洛谷 P4718 【模板】Pollard-Rho

Miller Rabin 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。

Pollard rho 是一个非常玄学的方式，用于在 O(n1/4)O(n^{1/4}) 的期望时间复杂度内计算合数 nn 的某个非平凡因子。事实上算法导论给出的是 O(p)O(\sqrt p)，pp 是 nn 的某个最小因子，满足 pp 与 n/pn/p 互质。但是这些都是期望，未必符合实际。但事实上 Pollard rho 算法在实际环境中运行的相当不错。

这里我们要写一个程序，对于每个数字检验是否是质数，是质数就输出 Prime；如果不是质数，输出它最大的质因子是哪个。

代码（1）
#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;
}