Home > Project Euler, python > Problem Euler #47

Problem Euler #47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 * 7
15 = 3 * 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2^2 * 7 * 23
645 = 3 * 5 * 43
646 = 2 * 17 * 19.

Find the first four consecutive integers to have four distinct primes factors.
What is the first of these numbers?

Analisi:
partiamo a ciclare dal minimo numero con 4 diversi fattori primi:
2*3*5*10 = 210

import time

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

primes = [pr for pr in xrange(1, 1000000) if is_prime(pr)]

def get_factors(n):
    factors = set()
    while n > 1:
        for p in primes:
            if n % p == 0:
                factors.add(p)
                n /= p
                break
    return factors


count = 1
res = 210 # 2*3*5*7
while count != 4:
    res += 1
    if len(get_factors(res)) == 4:
        count += 1
    else:
        count = 0

print "problem euler 47: {} \nelapsed time: {}sec".format(res-3, time.time() - 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: