检查一个数字是否是一个完全平方数 [英] Check if a number is a perfect square

问题描述

如何判断一个数是否为完全平方数?

速度无关紧要，目前，只需工作.

解决方案

依赖任何浮点计算的问题(math.sqrt(x), or x**0.5) 是你不能真正确定它是准确的(对于足够大的整数 x，它不会，甚至可能溢出).幸运的是(如果不急的话；-)有许多纯整数方法，例如以下...:

def is_square(apositiveint):x = apositiveint//2看到 = 设置([x])而 x * x != apositiveint:x = (x + (apositiveint//x))//2如果看到 x:返回 False看到.add(x)返回真对于范围内的 i (110, 130):打印 i, is_square(i)

提示:它基于平方根的巴比伦算法"，请参阅维基百科.它确实适用于任何正数，只要你有足够的内存来完成计算；-)

编辑:让我们看一个例子...

x = 12345678987654321234567 ** 2对于范围内的 i (x, x+2):打印 i, is_square(i)

根据需要打印(并且在合理的时间内打印；-):

1524157896666209426002111556165263283035677489 真152415789666209426002111556165263283035677490 假

请在您提出基于浮点中间结果的解决方案之前，确保它们在这个简单的示例中正常工作——这并不那难(您只需要一些额外的检查，以防 sqrt计算有点偏离)，只是需要一点小心.

然后尝试使用 x**7 并找到巧妙的方法来解决您将遇到的问题，

溢出错误:long int 太大，无法转换为浮点数

当然，随着数字的不断增长，您必须变得越来越聪明.

如果我赶时间，当然，我会使用gmpy -- 但是，我显然有偏见；-).

<预><代码>>>>导入 gmpy>>>gmpy.is_square(x**7)1>>>gmpy.is_square(x**7 + 1)0

是的，我知道，这太容易了，感觉就像作弊一样(有点像我对 Python 的总体感觉；-) -- 一点也不聪明，只是完美的直接和简单(而且，在 gmpy 的情况下，绝对的速度；-)...

How could I check if a number is a perfect square?

Speed is of no concern, for now, just working.

解决方案

The problem with relying on any floating point computation (math.sqrt(x), or x**0.5) is that you can't really be sure it's exact (for sufficiently large integers x, it won't be, and might even overflow). Fortunately (if one's in no hurry;-) there are many pure integer approaches, such as the following...:

def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

for i in range(110, 130):
   print i, is_square(i)

Hint: it's based on the "Babylonian algorithm" for square root, see wikipedia. It does work for any positive number for which you have enough memory for the computation to proceed to completion;-).

Edit: let's see an example...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

this prints, as desired (and in a reasonable amount of time, too;-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

Please, before you propose solutions based on floating point intermediate results, make sure they work correctly on this simple example -- it's not that hard (you just need a few extra checks in case the sqrt computed is a little off), just takes a bit of care.

And then try with x**7 and find clever way to work around the problem you'll get,

OverflowError: long int too large to convert to float

you'll have to get more and more clever as the numbers keep growing, of course.

If I was in a hurry, of course, I'd use gmpy -- but then, I'm clearly biased;-).

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

Yeah, I know, that's just so easy it feels like cheating (a bit the way I feel towards Python in general;-) -- no cleverness at all, just perfect directness and simplicity (and, in the case of gmpy, sheer speed;-)...

这篇关于检查一个数字是否是一个完全平方数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！