資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中無平方因子除數的最小數量
問題陳述
給定一個整數 N。找到無平方因子除數的最小數量。
N 的因式分解應該只包含那些不是完全平方的除數。
示例
如果 N = 24，則有 3 個無平方因子因子，如下所示：
因子 = 2 * 6 * 2
演算法
- 找到 N 的平方根以下的所有素因子。
- 現在，考慮所有小於或等於 N 的平方根的素因子，並對每個素因子找到其在數字 N 中的最大冪（例如，24 中 2 的最大冪為 3）。
- 現在，我們知道，如果一個素因子在 N 中的冪大於 1，則它不能與自身組合（例如，24 中 2 的冪為 3，因此 2 x 2 = 4 或 2 x 2 x 2 = 8 不能出現在 24 的因式分解中，因為它們都不是無平方因子），因為它將被某個完全平方數整除。
- 但是，一個素因子與另一個素因子（僅一次）組合將永遠不會被任何完全平方數整除。
- 這給了我們一個直覺，即答案將是數字 N 中所有素因子的最大冪的最大值。
示例
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1005
void getPrimes(vector<int>& primes) {
bool prime[MAX];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p < MAX; p++) {
if (prime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
}
for (int p = 2; p < MAX; p++)
if (prime[p])
primes.push_back(p);
}
int getMinimumSquareFreeDivisors(int n) {
vector<int> primes;
getPrimes(primes);
int maxCnt = 0;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
if (n % primes[i] == 0) {
int tmp = 0;
while (n % primes[i] == 0) {
tmp++;
n /= primes[i];
}
maxCnt = max(maxCnt, tmp);
}
}
if (maxCnt == 0)
maxCnt = 1;
return maxCnt;
}
int main() {
int n = 24;
cout << "Minimum number of square free divisors = " << getMinimumSquareFreeDivisors(n) << endl;
return 0;
}輸出
當你編譯並執行上述程式時，它會生成以下輸出：
Minimum number of square free divisors = 3
更新於： 2019-11-22
145 次瀏覽
廣告