【题目描述】

给定一个整数 n，请找出 n 的最大平方因子。所谓平方因子，就是一个 n 的因子，且是一个完全平方数。最大平方因子就是 n 的所有平方因子中最大的数。

如 12的最大平方因子为 4，81 的最大平方因子为其本身，21 的最大平方因子为 1。

【输入描述】

单个整数表示 n。

【输出描述】

单个整数表示 n 的最大平方因子。

【样例输入1】

12

【样例输出1】

4

【样例输入2】

81

【样例输出2】

81

【样例输入3】

21

【样例输出3】

1

【数据范围】

• 对于 50% 的数据，1≤n≤10000；

• 对于 100% 的数据，1≤n≤10,000,000。

【题目分析】

注意完全平方因子的概念即可。完全平方因子，首先是因子，其次是完全平方数，最后是这些中最大的那个。

【参考代码】

#include <bits/stdc++.h>  using namespace std;  int main() {  	int n=0,ans=0;  	int t=0; //临时值  	cin >> n;  	for (int i = 1; i  <= n; i++) {  		if(n%i==0){  			//说明i是因数，  			t = sqrt(i);  			if(t*t==i){  				ans=t*t;  //一直成立，取最后一个  			}  		}  	}  	cout << ans << endl;  	return 0;  }

或者反着来，这样找最大的速度会快一些

#include <bits/stdc++.h>  using namespace std;  int main() {      int n=0,ans=0;      int t=0; //临时值      cin >> n;      for (int i = n; i  >= 1; i--) {          if(n%i==0){              //说明i是因数，              t = sqrt(i);              if(t*t==i){                  ans=t*t;                  break;              }          }      }      cout << ans << endl;      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});