数学算法(算法竞赛、蓝桥杯）--分解质因数、唯一分解定理

作者：Cpp五条 | 2024-03-28 16:57:20

踩

1、B站视频链接：G07 分解质因数唯一分解定理试除法_哔哩哔哩_bilibili

题目链接：质因子分解 - 洛谷


#include <bits/stdc++.h>
using namespace std;
 
int n;
int a[100010];//质因子的个数
 
void decompose(int x){
	for(int i=2;i*i<=x;i++){//i增加，x减少，往中间靠拢 
		while(x%i==0){
			a[i]++;
			x/=i;
		}
	}
	if(x>1)a[x]++;
}
 
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		decompose(i);
	}
	for(int i=1;i<=n;i++){
		if(a[i]){
			cout<<i<<" "<<a[i]<<endl;
		}
	}
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/330039

数学算法(算法竞赛、蓝桥杯）--分解质因数、唯一分解定理

1、B站视频链接：G07 分解质因数 唯一分解定理 试除法_哔哩哔哩_bilibili

1、B站视频链接：G07 分解质因数唯一分解定理试除法_哔哩哔哩_bilibili