我將數字的素數分解為映射：std::map<int, int> m，其中 key 是素數，value 是該素數在產品中出現的次數。
示例：100 的素數分解是 2 * 2 * 5 *5，所以m[2] = 2, 和m[5] = 2
我的問題是如何獲得一個數字的所有除數的數量，因為它是素數分解（以上述形式）？
uj5u.com熱心網友回復：
除數的數量簡單地等于每個素數的計數加1的乘積。
這是因為您可以通過幾個嵌套回圈遍歷素數冪的所有組合來輕松恢復所有除數。每個回圈都遍歷單素數的冪。
嵌套回圈的不同迭代次數等于所有回圈大小的乘積。并且每個回圈的大小等于素數加一，因為您遍歷0, 1, 2, ..., PrimeCnt具有PrimeCnt 1數字的 powers 。
例如，對于100 = 2 * 2 * 5 * 5您有m[2] = 2and m[5] = 2，因此您希望將 2 的所有冪與 5 的所有冪組合，即將 2^0 或 2^1 或 2^2（這里是 3 個冪）與 5^0 或 5^1 或5^2（這里是 3 次方），因此 3 次方乘以 3 次方得到 9。
這也可以通過下面的簡單程式輕松驗證，該程式首先將所有除數計算為 的乘積PrimeCnt 1，然后通過迭代計算所有除數來驗證這一事實。
您可以輕松地將任意數量n的素數和映射m到下面的程式中以驗證其他情況。
在線嘗試！
#include <iostream>
#include <map>
int main() {
int n = 100;
std::map<int, int> m = {{2, 2}, {5, 2}};
int c = 1;
for (auto [k, v]: m)
c *= v 1;
std::cout << "Computed as product: " << c << std::endl;
int c2 = 0;
for (int i = 1; i <= n; i)
if (n % i == 0)
c2;
std::cout << "Computed through iteration: " << c2 << std::endl;
}
輸出：
Computed as product: 9
Computed through iteration: 9
uj5u.com熱心網友回復：
72.113.61 的所有除數的形式為 7^u.11^v.61^w，其中 0≤u≤2、0≤v≤3 和 0≤w≤1。因此有 (2 1).(3 1).(1 1) 組合。觀察圖案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/529173.html
標籤：C 算法
上一篇：二叉搜索樹懶洗掉Python
下一篇：堆排序實作Python