Home > Project Euler, python > Problem Euler #27

Problem Euler #27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

    n² + an + b, where |a| < 1000 and |b| < 1000

    where |n| is the modulus/absolute value of n
    e.g. |11| = 11 and |−4| = 4

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.

preso atto che ‘b’ deve essere un primo (google way):

import time
ts = time.clock()

def is_prime(n):
    if n <= 1 or n % 2 == 0: return False
    elif n == 2: return True
    else:
      i = 3
      r = int(n**0.5)
      while i <= r:
          if n % i == 0: return False
          i += 2
      return True

primes = (x for x in range(2,1000) if is_prime(x))

count, k, j = 0, 0, 0

for b in primes:
  for a in xrange(-999,1000,2):
      n=0
      while is_prime(n**2 + a*n + b):
          n += 1
      if n > count:
          count, k, j = n, a, b

print k*j
print time.clock() - ts
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: