备战蓝桥python——完全平方数

完全平方数

链接: 完全平方数

暴力解法：

n = int(input())
for i in range(1, n+1):if(((i*n)**0.5)%1==0.0):print(i)break

运用数论相关知识求解

任意一个正整数都可以被分解成若干个质数乘积的形式，例如 :$$20=2^2\ast 5^1$$

由此，我们不难分析出，只要分解出的质因数的幂次项均为偶数，这个数就是完全平方数了
如
$$100=2^2\ast 5^2$$
这就是我们寻找x的方法

搜索范围的问题

我们确定搜索范围为[1, int(n**0.5)]
我们是如何推导出来的呢？

1）如果这个数本身就是完全平方数，也就是：
$$100=2^2\ast 5^2$$
对100开根号结果为10，包含了两个质因数，那么我们肯定可以搜索到它的质因数

2）如果这个数本身不是完全平方数，也就是：
$$20=2^2\ast 5^1$$
对20开根号，取整得到4，在二者中间，并且后者幂次项为奇数，最后直接乘上就好了

完整代码

def zhi(x):for i in range(2, int(x**0.5)+1):if(x%i==0):return Falsereturn Truen = int(input())
ans=1
for i in range(2, int(n**0.5)+1):if(n%i==0 and zhi(i)):k=0while n%i==0:n/=ik+=1if(k&1):ans*=i
if(n>1):ans*=n
print(int(ans))