B3871 因数分解 题解

· · 题解

博客食用观感更佳

简要题意

给出一个正整数 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;
}

感谢阅读！