找n最大完全平方因子O(logn)

要找到一个数n的最大完全平方因子，并且时间复杂度为O(logn)，可以采用以下方法：

1. 从根号n开始向下遍历，找到最大的整数k，使得k的平方不超过n。
2. 如果k的平方正好等于n，则k就是最大的完全平方因子。
3. 如果k的平方小于n，则将k减半（因为k/2的平方一定小于k的平方），继续检查剩余的n是否能被k/2的平方整除。

以下是实现这一算法的C++代码示例：

#include <iostream>
#include <cmath>

// 函数用于找到最大的完全平方因子
int maxPerfectSquareFactor(int n) {
    int maxSquare = 0;
    int sqrt_n = std::sqrt(n);
    // 从sqrt_n开始向下遍历
    for (int i = sqrt_n; i >= 1; --i) {
        // 如果当前数i是n的因子，检查它是完全平方数且最大
        if (n % i == 0) {
            int sqrt_i = std::sqrt(i);
            if (sqrt_i * sqrt_i == i) {
                maxSquare = i; // 找到最大的完全平方因子
                break;
            }
        }
    }
    return maxSquare;
}

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;

    int result = maxPerfectSquareFactor(n);
    std::cout << "The largest perfect square factor is: " << result << std::endl;

    return 0;
}