数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告