擷取一個數的各個質數因子

這個題用到了題目的知識點，記錄一下吧。

假設s和m初始化，s = "a"; m = s;
再定義兩種操作，第一種操作：
m = s;
s = s + s;
第二種操作：
s = s + m;
求最小的操作步驟數，可以将s拼接到長度等于n           

思路：

思路：
實際上求的是m取得最大值最少需要幾步
因為s一定是m的倍數

當n為質數，則隻能通過步驟二來湊n
當n不是質數，将其拆分成各個質數，然後步驟就是每個質數的實作步驟           

将n拆分成各個質數因子的實作僞代碼

void minStep(int n){
	for(int i=2; i<=n; i++){
		while(n%i==0){
			此時的i就是n的一個質數因子了
			n/=i;
		}
	}
}           

整個題解：

/*
假設s和m初始化，s = "a"; m = s;
再定義兩種操作，第一種操作：
m = s;
s = s + s;
第二種操作：
s = s + m;
求最小的操作步驟數，可以将s拼接到長度等于n

思路：
實際上求的是m取得最大值最少需要幾步
因為s一定是m的倍數

當n為質數，則隻能通過步驟二來湊n
當n不是質數，将其拆分成各個質數，然後步驟就是每個質數的實作步驟
*/
#include<iostream>
#include<math.h>
using namespace std;

int CreateNum(){
	return rand();
}

//判斷一個數是不是質數
bool judge(int n){
	for(int i=2;i<=sqrt(n);i++){
		if(!n%i) return true;
	}
	return false;
}

void minStep(int n){
	cout<<"n的值為："<<n<<endl;
	if(n<2) return;

	//判斷n是不是質數
	bool zhishu=judge(n);
	if(zhishu){
		cout<<n-1<<endl;
		return;
	}	

	//不是質數，此時需要擷取質數的累加和以及質數的個數
	//f(n)=f(a*b*c*d)=a-1+b-1+c-1+d-1
	int sum=0, num=0;
	for(int i=2; i<=n; i++){
		//n的值會一直變小，當i=n時，說明這個n的各個質數因子被拆分完畢
		while(n%i==0){
			sum+=i;
			num++;
			n/=i;
		}
	}
	cout<<"最少次數為："<<sum-num<<endl;
}

int main(){
	int time=10, n=0;
	while(time--){
		n=CreateNum();
		minStep(n);
	}
	return 0;
}