如何有效地枚举所有完美的正方形？

Question

我做了以下程序，要求用户输入上限，并计算每个完美平方的上限打印&。不过，我认为我的is_perfect_square函数效率不高，因为当上限在数千或更多时，计算完美平方需要很长时间。我想知道如何让我的程序更高效，我认为使用数学模块来使用sqrt可以工作，但我不是数学家，所以请求帮助。 我的计划是：

"""Print all the perfect squares from zero up to a given maximum.""" 
import math 

def read_bound(): 
    """Reads the upper bound from the standard input (keyboard). 
     If the user enters something that is not a positive integer 
     the function issues an error message and retries 
     repeatedly""" 
    upper_bound = None 
    while upper_bound is None: 
     line = input("Enter the upper bound: ") 
     if line.isnumeric() and int(line) >= 0: 
      upper_bound = int(line) 
      return upper_bound 
     else: 
      print("You must enter a positive number.") 



def is_perfect_square(num): 
    """Return true if and only if num is a perfect square""" 
    for candidate in range(1, num): 
     if candidate * candidate == num: 
      return True 



def print_squares(upper_bound, squares): 
    """Print a given list of all the squares up to a given upper bound""" 


    print("The perfect squares up to {} are: ". format(upper_bound)) 
    for square in squares: 
     print(square, end=' ') 



def main(): 
    """Calling the functions""" 
    upper_bound = read_bound() 
    squares = [] 
    for num in range(2, upper_bound + 1): 
     if is_perfect_square(num): 
      squares.append(num) 

    print_squares(upper_bound, squares) 


main() 

Answer 1

你可以使用sqrt

import math 
def is_perfect_square(num): 
    """Return true if and only if num is a perfect square""" 
    root = math.sqrt(num) 
    return int(root) - root == 0 

或@PacoH表明：

return root.is_integer() 

Answer 2

正如你所说的使用math.sqrt：

import math 


def is_perfect_square(num): 
    """Return true if and only if num is a perfect square""" 
    return math.sqrt(num).is_integer() 

Answer 3

upper_bound = int(input('Enter the upper bound: ')) 

upper_square_root = int(upper_bound**(1/2)) 

print([i**2 for i in range (1, upper_square_root+1)]) 

实施例输出为界78：：

0 I将完全由第一把你的上限的平方根，然后打印每个正整数更少或相等该数的平方反转逻辑

[1,4,9,16,25,36,49,64]

这样可以避免大量不必要的循环和数学计算。

Answer 4

广场是奇数的部分和：

1 = 1 
4 = 1 + 3 
9 = 1 + 3 + 5 
16 = 1 + 3 + 5 + 7 

所以，你可以简单地这样做：

square = 1 
    odd = 1 
    while square <= upper_bound: 
    print(square) 
    odd = odd + 2 
    square = square + odd 

https://ideone.com/dcnEVJ

无需平方根或检查每个号码。它并没有比这更快。