算法笔记5.5 质因子分解
不断除以2~sqrt(n)内的素数表,求出每个素数的个数
结构体:
struct factor{
int x;//质因子
int cnt;//质因子个数
}fac[10];//int范围内10个够了
循环出完后n为1,正常
n不为1,说明n本来就是质数,质因子是本身>sqrt(n)
eg:分解质因数
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e6;
bool p[N]={0};
int prime[N],pNum=0;
int facNum;//质因子个数
struct factor{
int x;//质因子
int cnt;//质因子个数
}fac[10];//int范围内10个够了
//求素数表
void Find_Prime(){
for(int i=2;i<N;i++){
if(p[i]==false){
prime[pNum++]=i;
for(int j=i+i;j<N;j+=i){
p[j]=true;
}
}
}
}
//分解质因数
void qfd(int n){
facNum=0;
int sqr=(int)sqrt(n);
for(int i=0;i<pNum&&prime[i]<=sqr;i++){
if(n%prime[i]==0){
fac[facNum].x=prime[i];
fac[facNum].cnt=0;
while(n%prime[i]==0){
fac[facNum].cnt++;
n/=prime[i];
}
facNum++;
}
}
//n本身是质数
if(n>1){
fac[facNum].x=n;
fac[facNum].cnt=1;
facNum++;
}
}
void showResult(){
bool isFirst=true;
for(int i=0;i<facNum;i++){
for(int j=0;j<fac[i].cnt;j++){
if(isFirst) {
cout<<fac[i].x;
isFirst=false;
}
else cout<<"*"<<fac[i].x;
}
}
cout<<endl;
}
int main(){
Find_Prime();
int n;
while(cin>>n){
qfd(n);
cout<<n<<"=";
showResult();
}
return 0;
}