C ++中最小平方除数的数量
问题陈述
给定整数N。求平方除数的最小数量。
N的因式分解应仅包含那些不是全平方的除数
示例
如果N=24，则存在3个平方自由因数，如下所示-
因素=2*6*2
算法
找出所有素数直到N的平方根
现在，考虑所有小于或等于N的平方根的素数，并为每个素数找到其最大幂数N（例如24中2的最大幂为3）
现在，我们知道如果素数的幂大于N的1，则无法将其与自身分组（例如2具有24的3的幂，因此2x2=4或2x2x2=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