Số lượng chia ô vuông miễn phí tối thiểu trong C ++

Tuyên bố vấn đề

Cho một số nguyên N. Tìm số ước số bình phương tự do nhỏ nhất.

Sự phân chia nhân tử của N chỉ nên bao gồm những ước số không phải là bình phương đầy đủ

Ví dụ

Nếu N =24 thì có 3 hệ số tự do bình phương như sau -

Yếu tố =2 * 6 * 2

Thuật toán

• Tìm tất cả các thừa số nguyên tố đến căn bậc hai của N
• Bây giờ, hãy xem xét tất cả các thừa số nguyên tố nhỏ hơn hoặc bằng căn bậc hai của N và đối với mỗi thừa số nguyên tố, hãy tìm lũy thừa lớn nhất của nó trong số N (như lũy thừa tối đa của 2 trong 24 là 3)
• Bây giờ, chúng ta biết rằng nếu một thừa số nguyên tố có lũy thừa lớn hơn 1 trong N, thì nó không thể được nhóm với chính nó (ví dụ:2 có lũy thừa 3 trong 24, do đó 2 x 2 =4 hoặc 2 x 2 x 2 =8 không thể xảy ra trong thừa số của 24 vì cả hai đều không phải là bình phương tự do) vì nó sẽ chia hết cho một số bình phương hoàn hảo
• Nhưng một thừa số nguyên tố được nhóm với một thừa số nguyên tố khác (chỉ một lần) sẽ không bao giờ chia hết cho bất kỳ bình phương hoàn hảo nào
• Điều này cho chúng ta trực giác rằng câu trả lời sẽ là giá trị tối đa của lũy thừa tối đa của tất cả các thừa số nguyên tố trong số N

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum number of square free divisors = 3