问题是如何高效地在输入的数字非常大时,在给定范围内找到完全平方数。我的解决方法导致“超时”错误。我已经查看了以下链接,但它们没有解决我的问题:
- 关于完全平方数的Python程序
- 如何检查一个数字是否为完全平方数?
- 确定一个整数的平方根是否为整数的最快方法(我不知道如何在Python中实现该链接中给出的解决方案)。
- 关于完全平方数的Python程序
- 如何检查一个数字是否为完全平方数?
- 确定一个整数的平方根是否为整数的最快方法(我不知道如何在Python中实现该链接中给出的解决方案)。
问题描述为:
输入格式:第一行包含T,表示测试用例的数量。每个测试用例都以换行符分隔,并且包含两个以空格分隔的整数A和B。在范围A和B(含两端)中找到所有的完全平方数。
示例输入:
2 3 9 17 24
我编写的代码是:
import math
def is_perfect_square(n):
return n % n**0.5 == 0
t = int(raw_input())
for i in range(t):
numbers = map(int, raw_input().split())
count = 0
for j in xrange(numbers[0], numbers[1] + 1): # I also tried range() which gave memory error
if (is_perfect_square(j)):
count = count + 1
print count
虽然这段代码对于较小的数字是有效的,但对于大输入会出现“超时”错误。
(注意:gmpy
不是一个选项,因为该代码必须在没有gmpy
模块的在线编译器上运行)
floor
和ceiling
。而且在sqrt
结果中需要小心四舍五入。 - Mark Ransoma = int(math.ceil(math.sqrt(x)))
和b = int(math.floor(math.sqrt(x)))
然后print (b + 1) - a
就完成了任务。 - titan7585