Wie man alle perfekten Quadrate effizient aufzählt?

Question

Ich habe das folgende Programm gemacht, das für eine Benutzereingabeobergrenze anfragt und berechnet & Drucke jedes perfekte Quadrat bis zur Obergrenze. Allerdings denke ich, dass meine is_perfect_square Funktion nicht sehr effizient ist, da es lange dauert, die perfekten Quadrate zu berechnen, wenn die obere Grenze in den Tausenden oder mehr liegt. Ich frage mich, wie ich mein Programm effizienter machen kann, ich denke, mit dem Mathe-Modul mit sqrt könnte funktionieren, aber ich bin kein Mathematiker so um Hilfe bitten. Mein Programm ist:

"""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

Sie 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 

oder als @PacoH zeigte verwenden:

return root.is_integer() 

Answer 2

Wie Sie math.sqrt die Verwendung:

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

I würde die Logik vollständig umkehren, indem zuerst die Quadratwurzel Ihre Obergrenze nimmt, dann den Druck auf den Platz jeder positive ganze Zahl kleiner oder gleich dieser Zahl:

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)]) 

Beispiel Ausgang für gebundene 78:

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

Auf diese Weise können viele unnötige Schleifen und mathematische Berechnungen vermeiden.

Answer 4

Quadrate sind die Teilsummen der ungeraden Zahlen:

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

So können Sie einfach tun:

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

https://ideone.com/dcnEVJ

Keine Notwendigkeit für Quadratwurzel oder jede Nummer zu überprüfen. Es geht nicht viel schneller als das.