C ++中最小平方除数的数量

问题陈述

给定整数N。求平方除数的最小数量。

N的因式分解应仅包含那些不是全平方的除数

示例

如果N = 24，则存在3个平方自由因数，如下所示-

因素= 2 * 6 * 2

算法

• 找出所有素数直到N的平方根

• 现在，考虑所有小于或等于N的平方根的素数，并为每个素数找到其最大幂数N（例如24中2的最大幂为3）

• 现在，我们知道如果素数的幂大于N的1，则无法将其与自身分组（例如2具有24的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