Elenco di numeri i cui quadrati sono la somma di due quadrati

Question

Ho appena iniziato a imparare Python e ho iniziato a fare alcuni problemi solo per aiutare a costruire le mie abilità, tuttavia sono abbastanza bloccato su questa domanda.

Creare un elenco contenente tutti gli interi positivi fino a 1000 i cui quadrati possono essere espressi come somma di due quadrati, (i, e., Numeri interi p per cui p^2 = m^2 + n^2, dove m e n sono numeri interi maggiori di 0.)

Suggerimenti: ci sono diversi approcci. Potresti trovare utile avere un elenco di tutti i numeri quadrati. L'operatore in potrebbe essere utile.

Ecco il codice che mi è venuta in mente finora:

numbers=xrange(1001) 
    numbers_squared=[x**2 for x in numbers] 
    a=[] 

    for x in numbers_squared: 
     for b in numbers_squared: 
      if (x+b)**.5 <= 1001: 
       a.append(x+b) 
    print a 

Il problema che ottengo con questo è che Python vogliono anni per fare questi calcoli (ho aspettato circa dieci minuti ed è ancora numeri di stampa). Qualsiasi suggerimento su come risolvere questo sarebbe molto apprezzato.

p.s. Il punto principale è usare le liste. Anche i suggerimenti sarebbero più apprezzati della soluzione stessa.

Grazie!

Answer 1

come su una lista di comprensione? calcolare per c nella gamma (1,1011) per B nella gamma (1, c) per una nella gamma (1, b)

come segue:

x = [(a,b,c) for c in range(1,1001) for b in range(1, c) for a in range(1,b) if a**2+b**2==c**2] 
print x 

ho cronometrato questo e ci vogliono 46 secondi per completare sul mio computer

Answer 2

Prima di tutto, non stai risolvendo il problema. Devi fare un controllo per assicurarti che (x+b)**.5 sia effettivamente un numero intero. In secondo luogo, se si stampano numeri, si sono già calcolati tutti i numeri. Fare quanto sopra ridurrà il tempo richiesto per questo passaggio.

Answer 3

Questo potrebbe funzionare:

def isSumOfSquares(n): 
    """return True if n can be expressed as the sum of two squares; False otherwise""" 

    for a in xrange(1,n): 
     b = n-(a**2) 
     if b<=0: 
      return False 
     elif not math.sqrt(b)%1: 
      return True 
    return False 

answer = [i for i in xrange(1,1001) if isSumOfSquares(i**2)] 

Fatemi sapere se questo funziona per voi

Answer 4

Ho appena answered this altrove!

import math 

def is_triple(hypotenuse): 
    """return (a, b, c) if Pythagrean Triple, else None""" 
    if hypotenuse < 4: 
     return None 

    c = hypotenuse ** 2 

    for a in xrange(3, hypotenuse): 
     b = math.sqrt(c - (a ** 2)) 
     if b == int(b): 
      return a, int(b), hypotenuse 

    return None 

>>> results = [x for x in range(1001) if is_triple(x)] 
>>> len(results) 
567 

Corre quasi all'istante.