第一种，试除法

第二种，先求质数，在试除质数

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

std::vector<int> res;
std::vector<int> primes;
int len;
void input(){
cin >> len;
}

void calc(){
int nn = len;
std::vector<int>().swap(res);
for (int i = 2 ; i <= len ; i++){
//cout << nn << " " << i<<endl;
if (nn == 1){
return;
}
if (nn == i){
res.push_back(i);
return;
}
while(nn%i == 0){
res.push_back(i);
nn/=i;
}
}
}

void calc2(){
int nn = len;
std::vector<int>().swap(res);
for (int i = 0 ; i <= primes.size() ; i++){
//cout << nn << " " << i<<endl;
if (nn == 1){
return;
}
if (nn == primes[i]){
res.push_back(primes[i]);
return;
}
while(nn%primes[i] == 0){
res.push_back(primes[i]);
nn/=primes[i];
}
}
}

void output(){
cout << len<<":";
for (int i = 0 ; i < res.size(); i++){
cout << res[i] << " ";
}
cout << endl;
}

void getPrime0(int n){
bool m;
for(int i = 2; i <= n; i ++){
m = true;
for(int j = 0; j < primes.size(); j++){
if(i % primes[j] == 0){
m = false;
break;
}
}
if(m){
primes.push_back(i);
}
}
// for(int i = 0 ; i < primes.size() ; i++){
// cout << primes[i]<< " ";
// }
// cout << endl;

}

int main(){
int a = 99999;
getPrime0(a);
while(true)
{
input();
//calc();
calc2();
output();
}

return 0;
}

因式分解