Voici un résumé de l'énoncé du problème 27 "Quadratic primes" du Project Euler (traduction complète en français ici) :

Find the product of the coefficients, \(a\) and \(b\), for the quadratic expression that produces the maximum number of primes for consecutive values of \(n\), starting with \(n = 0\).

Compréhension du problème

Reformulons le problème : il nous faut trouver le produit des coefficients a et b du polynôme \(P(n) = n^2 + an + b\) qui produit le plus grand nombre de nombres premiers pour des valeurs consécutives de n en commençant à \(n = 0\). La façon la plus simple, je pense, pour résoudre ce problème est alors de trouver le nombre de nombres premiers que produisent tous les polynômes pour \(a, b \in ]1000; 1000[\). Toutefois, par simple observation, nous pouvons réduire de manière conséquente cet intervalle car nous pouvons voir que :

• pour que \(P(0)\) soit premier, \(P(0)\) étant égal à \(b\), \(b\) doit être premier
• pour que \(P(1)\) soit premier, \(b\) étant premier donc impair (sauf pour 2) et \(P(1)=1+a+b\), \(a\) doit être impair car si \(a\) est pair, alors \(1+a\) est impair, donc \(1+a+b\) est pair, donc \(P(1)\) n'est pas premier.

Le programme

Voici donc le programme Python que nous pouvons utiliser :

def primes_below(end):
    if end < 2:
        return []
    lng = (end//2) - 1
    primes = [True]*lng  
    for i in range(int(lng**0.5)):  
        if primes[i]:
            for j in range(2*i*(i + 3) + 3, lng, 2*i + 3):
                primes[j] = False  
    return [2] + [i*2 + 3 for i, j in enumerate(primes) if j]
#Obtention de la liste des nombres premiers inférieurs à 1000
primes = primes_below(1000)
longest = 0
#b prend successivement la valeur des différents nombres premiers
for b in primes:
    #a prend successivement la valeur de tous les nombres impairs de -999 à 2
    for a in range(-999, 1000, 2):
        image = b
        n = 0
        #Calcul du nombre consécutif de nombres premiers
        while functions.is_prime(image):
            n += 1
            image = n**2 + a*n + b
        if n > longest:
            longest = n
            resultat = a*b
print(resultat)

Notez que ce programme utilise la fonction "primes_below" qui permet d'obtenir tous les nombres premiers inférieurs à un certain nombre. Cette fonction est explicitée dans cet article.

Le résultat

La réponse à ce problème est -59231.