Home > Project Euler, python > Project Euler #60

Project Euler #60

The primes 3, 7, 109, and 673, are quite remarkable.
By taking any two primes and concatenating them in any order
the result will always be prime.
For example, taking 7 and 109, both 7109 and 1097 are prime.
The sum of these four primes, 792, represents the lowest sum
for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any
two primes concatenate to produce another prime.

python:

import time
import itertools as it

ts = time.time()

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


def conc_primes(n, m):
    return is_prime(int(str(n) + str(m))) and is_prime(int(str(m) + str(n)))

def prime_pairs(iterable):
    for n, m in it.combinations(iterable, 2):
        if not conc_primes(n, m): return False
    return True

primes = [n for n in xrange(3,10000,2) if is_prime(n)] + [2]

def get_five():
    for n in primes:
        for m in primes[primes.index(n):]:
            if conc_primes(n ,m):
                for x in primes[primes.index(m):]:
                    if prime_pairs([x, n, m]):
                        for y in primes[primes.index(x):]:
                            if prime_pairs([y, x, n, m]):
                                for z in primes[primes.index(y):]:
                                    if prime_pairs([z, y, x, n, m]):
                                        return sum([z, y, x, n, m])

res = get_five() 
print "euler 60: {}\nelapsed time: {}sec".format(res, time.time() - ts)
Categorie:Project Euler, python
  1. gennaio 13, 2014 alle 9:54 am

    I comment when I like a post on a website or I have something to add to the conversation.
    It’s a result of the fire communicated in the article I browsed.
    And on this post Project Euler #60 | bancaldo™.
    I was actually excited enough to drop a leave a responsea response🙂 I actually do have 2 questions for you if you do not mind.
    Is it only me or does it look like like some of the
    comments look like written by brain dead people?😛 And, if you are posting on other sites, I’d like to keep up with everything new you have to post.

    Would you make a list every one of all your shared sites like
    your twitter feed, Facebook page or linkedin profile?

  2. febbraio 12, 2014 alle 12:51 pm

    This site was… how do you say it? Relevant!! Finally I’ve found something which
    helped me. Appreciate it!

  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: