3077 分解质因子.md

3077 分解质因子

Description

给出一个正整数N（N<=32767)，要求将其分解成质因子的连乘积。
例如：当N=24时
结果为：24=222*3
又如；当N=13时
输出结果为：13=13

Input

一个数字N

Output

如题

Sample Input

12

Sample Output

12=2*2*3

HINT

---

#include <bits/stdc++.h>
using namespace std;
bool pri(long long n) {
    if (n<=3) {
        if(n>1) return true;
        else return false;
    } else if (n%2==0||n%3==0) {
        return false;
    } else {
        for (int i=5;i*i<=n;i+=6)
            if (n%i==0||n%(i+2)==0) return false;
        return true;
    }
}
int main() {
    int n=0,i=2;
    cin>>n;
    cout<<n<<"=";
    for(;n>1;i++) {
        if(pri(i)){
            if(n%i==0){
                n/=i;
                if(n==1){
                    cout<<i;
                }else{
                    cout<<i<<"*";
                }
                i=1;
            }
        }
    }
    cout<<endl;
    return 0;
}