資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究C++ 中一個大數的質數因子
在這個問題中，我們給定一個整數 N <= 10^18。我們的任務是列印該數的所有質因數及其出現的頻率。
我們舉個例子來理解問題：
Input: 100 Output: 2 2 5 2 Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.
要解決這個問題，我們必須找到這個數的質因數，然後計算它們的頻率。
為此，我們將檢查 2 作為因子的頻率，然後用 2 除以該數。然後，從 3 到平方根 n 檢查。除以每個作為該數因子的質數並增加其頻率。如果該數變為 1 則停止。然後列印所有質數及其頻率。
以下程式碼顯示了我們解決方案的實現：
示例
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
}輸出
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1
更新於： 2020 年 2 月 3 日
926 次瀏覽
廣告