自动搬运

查看原文

来自洛谷，原作者为

	Clarinet You are what you love.

搬运于2025-08-24 21:15:37，当前版本为作者最后更新于2023-10-22 13:24:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

博客食用观感更佳

简要题意

给出一个正整数 $N$，求它的因数分解式。

分析

题目不难，就是得注意一下细节。

不过既然在入门题库，就给像我一样的萌新讲解一下原理。最简单的做法，是直接从小开始遍历因数。

举个例子，最开始的 $2$ 和 $3$ 都是质数。假如这个数有一个合数因数 $6$，那么这个因数 $6$ 一定在刚才被替换为 $2$ 和 $3$ 了，所以直接从小找因数输出的一定全是质数。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a;
int p=0;
int main(){
	cin>>n;
	a=n;
	for(long long i=2;i<=sqrt(n);i++){
		if(a%i==0){
			int s=0;
			while(a%i==0){
				a/=i;
				s++;
			}
			if(p)cout<<"* ";
			if(s!=1)cout<<i<<"^"<<s<<" ",p=1;
			else cout<<i<<" ",p=1;
		}
	}
	if(a!=1){
		if(a!=n)cout<<"* "<<a;
		else cout<<a;
	}
	return 0;
}

感谢阅读！