算法筆記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;
}