文章目錄

• • 題目分析
  • 題目鏈接

題目分析

暴力求質(zhì)因數(shù)

下面i就是質(zhì)因子，s是質(zhì)因子i的階數(shù)。

暴力的時間復雜度O(n)，會超時

void divide(int n){for(int i=2;i<=n;i++){if(n%i==0){ //i是質(zhì)因子，因為2，3等都把各自的倍數(shù)篩完了int s=0;//統(tǒng)計質(zhì)因子的階數(shù)while(n%i==0){s++;n/=i;}cout<<i<<" "<<s<<endl;}} }

優(yōu)化

給出一個重要性質(zhì)：正整數(shù)n的因子中，最多包含1個大于$\sqrt{n}$的質(zhì)因子。（可以用反證法來證明）

這里試除法的優(yōu)化就是枚舉到$\sqrt{n}$，然后剩下的1個大于$\sqrt{n}$的質(zhì)因子單獨處理，這樣試除法分解質(zhì)因數(shù)的時間復雜度O($\sqrt{n}$)

ac代碼

#include<bits/stdc++.h> using namespace std;int n; int main(){cin >> n;cout<<n<<"=";if(n==1) cout<<1<<endl;else{bool is_first=true; //輸不輸出*//篩質(zhì)因子,枚舉到≤ 根號nfor(int i = 2; i<= n / i; i++){//i是質(zhì)因子，因為2，3等都把各自的倍數(shù)篩完了if(n% i == 0) {int k =0; //統(tǒng)計次數(shù)while(n % i ==0) n/=i ,k++;if(!is_first) cout<<"*";else is_first = false;cout << i;if(k>1) cout<<"^"<<k;}}//大于根號n的那個唯一的因子if(n >1){if(!is_first) cout<<"*";cout<< n;}}}

題目鏈接

PAT甲級1059 Prime Factors

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1059 Prime Factors ：[C++题解]分解质因子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。