Số ước số không chứa bình phương tối thiểu trong C++

Đề bài

Cho số nguyên N. Tìm số lượng ước số không chứa bình phương tối thiểu.

Phân tích thừa số của N nên chỉ bao gồm các ước số không phải là bình phương hoàn hảo.

Ví dụ

Nếu N = 24 thì có 3 ước số không chứa bình phương như sau:

Ước số = 2 * 6 * 2

Thuật toán

• Tìm tất cả thừa số nguyên tố đến căn bậc hai của N
• Xét tất cả thừa số nguyên tố ≤ √N và với mỗi thừa số nguyên tố tìm lũy thừa lớn nhất trong N (ví dụ lũy thừa lớn nhất của 2 trong 24 là 3)
• Nếu một thừa số nguyên tố có lũy thừa > 1 trong N, nó không thể nhóm với chính nó (ví dụ 2 có lũy thừa 3 trong 24, do đó 2x2=4 hoặc 2x2x2=8 không thể xuất hiện trong phân tích 24 vì cả hai đều không phải là không chứa bình phương) vì nó sẽ chia hết cho một bình phương hoàn hảo
• Nhưng một thừa số nguyên tố nhóm với 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 đáp án sẽ là giá trị lớn nhất của các lũy thừa lớn nhất của tất cả thừa số nguyên tố trong 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 << "Số ước số không chứa bình phương tối thiểu = " << getMinimumSquareFreeDivisors(n) << endl;
    return 0;
}

Kết quả

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:

Số ước số không chứa bình phương tối thiểu = 3