Primes quadratiques

Question

Je pose la question à propos du problème Project Euler 27 (https://projecteuler.net/problem=27). J'ai écrit un morceau de code qui ne fonctionne pas ou qui ne fonctionne pas assez vite. Je suis novice en programmation et je ne comprends pas bien la signification de l'erreur que je reçois. Quoi qu'il en soit, la question est de savoir quels entiers $ a, b $ avec $ | a |, | b |

< 1000 $ conduisent à $ n^2 + an + b $ produisant la plus grande collection de nombres premiers consécutifs commençant par $ n = 0 $. Tout d'abord, nous remarquons que $ b $ doit être lui-même premier pour que le terme $ n = 0 $ soit premier et commence la chaîne. J'ai donc écrit un morceau de code qui boucle b sur toutes les valeurs principales possibles puis vérifie chaque entier $ -1000 < un < 1000 $ et mesure la longueur de la chaîne des nombres premiers consécutifs produits. Je l'ai inclus ci-dessous:

n=int(input("Set a bound for range of a and b: ")) 


def is_prime(n): 
if n==1: 
    return False 
elif n==2 or n==3: 
    return True 
elif (n % 2 == 0) or (n % 3 == 0): 
    return False 
elif all(n % i != 0 for i in range(2, ceil(n**0.5+1))): 
    return True 
else: 
    return False 

def seive(n): 
primes=[] 
for i in range(n): 
    if is_prime(i)==True: 
     primes.append(i) 
for j in primes: #j can't be allowed to be negative since when m=0 (the first term), we must have m**2+k*m+j prime. Therefore j must be chosen from primes 
    for k in range(-n,n,1): 
     chain=[] 
     for m in range(0,n): 
      while is_prime(m**2+k*m+j) == True and m**2+k*m+j>0: 
       chain.append(m**2 + k*m + j) 
       details = [j,k,len(chain)] 
return details 

print(seive(n)) 

Quelqu'un pourrait-il s'il vous plaît expliquer soit ce que je l'ai fait mal et me donner un indice sur la façon de le faire fonctionner? Merci!

Answer 1

L'analyse du problème génère deux contraintes, par ex. que b doit être premier ou qu'un doit être supérieur à 1 - b. Cependant, la gamme possible pour a et b est si minuscule qu'il ne vaut pas la peine de trouver de telles contraintes et de les intégrer dans la solution - cela crée seulement des opportunités supplémentaires de faire des erreurs et de se tirer dans le pied.

La seule contrainte digne de considération est que n^2 + a*n + b doit être divisible par n lorsque n est un multiple de b. Par conséquent, la chaîne de nombres premiers doit s'arrêter à n = b au plus tard, ce qui donne un plafond pour le nombre maximum possible qui pourrait devoir être vérifié pour la primalité. C'est-à-dire que le plus grand candidat possible pour le test de primalité doit être inférieur à 2 000 000. Cela donne une limite utile lors de l'utilisation de l'appartenance à un ensemble au lieu de la division d'essai en tant que test de primalité. Comme rossum l'a laissé entendre dans un commentaire, la tâche n'est pas de trouver le dernier ensemble de coefficients testé et la longueur de chaîne résultante. On vous demande de trouver les coefficients a et b qui donnent la plus longue chaîne de nombres premiers et d'imprimer le produit de cette paire. Par conséquent, vous devez changer la façon dont vous traitez le «test en chaîne» et ses résultats.

Peut-être que vous comprendrez votre code mieux si vous le nettoyer un peu et de supprimer les redondances (par exemple is_prime(x) implique x >= 2 et donc x > 0, il ne vient pas de sens de mettre un test pour positiveness après un test de primalité) . Il devrait également être utile de refactoriser le code de manière à ce que les morceaux individuels aient une seule responsabilité et puissent être testés/réglés séparément avant d'être intégrés dans le tout. Une fois que vous avez mis votre code en forme, vous pouvez le poster sur Code Review, ce qui est un endroit beaucoup plus approprié pour le genre de commentaires que vous semblez rechercher. Les contraintes comme celles que j'ai mentionnées au début deviennent très intéressantes lorsque vous essayez de pousser l'enveloppe, mais pour résoudre le problème comme indiqué, il est préférable d'opter pour la solution la plus simple possible. Cela ne devrait pas prendre plus de quelques fractions de seconde même en Python.