Tìm số nhỏ nhất chia cho n để thành số chính phương trong C++

Cho N, tìm số nhỏ nhất chia N để kết quả là số chính phương. Ví dụ N=50 → 2 (50/2=25).

Số chính phương có các thừa số nguyên tố với số mũ chẵn. Phân tích thừa số nguyên tố N, nhân các thừa số có mũ lẻ.

Ví dụ

#include<iostream> #include<cmath> using namespace std; int findMinimumNumberToDivide(int n) {    int prime_factor_count = 0, min_divisor = 1;    while (n%2 == 0) {       prime_factor_count++;       n /= 2;    }    if (prime_factor_count %2)    min_divisor *= 2;    for (int i = 3; i <= sqrt(n); i += 2) {       prime_factor_count = 0;       while (n%i == 0) {          prime_factor_count++;          n /= i;       }       if (prime_factor_count%2)       min_divisor *= i;    }    if (n > 2)    min_divisor *= n;    return min_divisor; } int main() {    int n = 108;    cout << "Minimum number to divide is: " << findMinimumNumberToDivide(n) << endl; }

Kết quả

Minimum number to divide is: 3