Resposta do problema 050 - Consecutive prime sum

Resolvi esse problema utilizando força-bruta, demorou 692 segundos.

O objeivo desse problema é encontrar o número primo abaixo de 1000000 que seja originado da maior sequência de números primos.

Consecutive prime sum

Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Link para a pergunta: https://projecteuler.net/problem=50



Criei o seguinte script para resolver o problema:

def is_prime(n):
 if n == 2 or n == 3: return True
 if n < 2 or n%2 == 0: return False
 if n < 9: return True
 if n%3 == 0: return False
 r = int(n**0.5)
 f = 5
 while f <= r:
  #print('\t',f)
  if n%f == 0: return False
  if n%(f+2) == 0: return False
  f +=6
 return True

# lista que armazena todos os números primos até o limite desejado que no caso do problema é < 1000000
lista_primos = []

# número máximo pra verificar, no caso do problema é 1000000
limite = 1000000

# preenche a lista lista_primos com os números primos até o valor da variável limite
for x in range(1, limite):
 if is_prime(x):
  lista_primos.append(x)

def maior_numero_soma_seq(lista):
 i = 0
 lista.reverse()
 maior_numero_lista = max(lista)
 maior_sequencia = 0
 maior_numero = 0
 soma = []
 tamanho_lista = len(lista)
 while i < len(lista):
  j = i + 1
  soma.clear()
  soma.append(lista[i])
  while j < len(lista):
   if lista[j] < lista[i]:
    soma.append(lista[j])
    # fiz isso para que se o sum da lista soma for maior que o maior numero da lista
    # ele já passa e muda o indice i do while, ou seja passa para o próximo número
    # de início
    if sum(soma) > maior_numero_lista:
     j = len(lista) + 1
    else:
     if sum(soma) in lista:
      if len(soma) > maior_sequencia:
       maior_sequencia = len(soma)
       maior_numero = sum(soma)
       print("Maior sequencia = ",maior_sequencia)       
       print(soma, "=" , maior_numero)
       print("Indice i =", i,"de", tamanho_lista, "- % analisados =", (i/tamanho_lista)*100,"%")
       print("------------------------------------")
   j += 1
  i += 1
 return maior_numero

print("Resposta =", maior_numero_soma_seq(lista_primos))

Resposta (answer) - Selecione a linha abaixo para ver a resposta

997651

O script funciona da seguinte forma: crio uma lista com todos os números primos, depois vou analisando um a um com todas as somas possíveis (a soma tem que ser um número primo na lista).

Coloquei uns "print" para ver a evolução do processamento.

A medida que vai processando vai ficando cada vez mais lento, futuramente pretendo otimizar esse script.



Outras respostas postadas por outros usuários:

Usuário: dpinchbe

def primesieve(n):
    '''Sieve of Eratosthenes as suggested in Hans Riesel's Book'''
    ilist=[k for k in range(3,n+1,2)] #list of odds

    index=0
    p=3
    while p*p <= 2*((n-1)//2):   #only looking at oddsmax(P):
            return []
        if sum(P[k:k+length]) in P:
            return [P[k:k+length],sum(P[k:k+length])]
    return []

length=546  #I checked that 2+3+...+P_546 exceeds one million
while not is_sum(length):
    length-=1

answer=is_sum(length)
psum,firstp=answer[1],answer[0][0]
print(psum," is the sum of ",length," consecutive primes")
print("starting with ",firstp)

Usuário: skasch

def prm(n):
    f = [True] * n
    for i in [2] + list(range(3, int(sqrt(n)) + 1, 2)):
        if f[i]:
            f[2*i::i] = [False] * len(f[2*i::i])
    return [i for i in [2] + list(range(3, n+1, 2)) if f[i]]
N = 1000000
ps = prm(N)
n = 0
ms = 0
while ms < N:
    ms += ps[n]
    n += 1
r = 0
for l in reversed(range(n)):
    i0 = 0
    while sum(ps[i0:i0+l]) < N:
        if sum(ps[i0:i0+l]) in ps:
            r = sum(ps[i0:i0+l])
        i0 += 1
    if r != 0:
        break
print(r)