分解质因数

参考资料

• 分解质因数 - OI Wiki

朴素算法

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;

例题

洛谷 B3715 分解质因子 2

洛谷 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$。

Code (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;
}