Euler Solution 47

From ProgSoc Wiki

Jump to: navigation, search

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² × 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?

Solutions for Problem 47

Python by Althalus

Runtime: 16 seconds

import time, math
start_time = time.time()

def isPrime(num):
        for i in range(2,int(math.sqrt(num))+1):
                if num%i == 0:
                        return False
        return True

def getPrimeFactors(num):
        numbers=[]
        for i in range(2,int(math.sqrt(num))+1):
                if num%i == 0:
                        if isPrime(i): numbers.append(i)
                        if isPrime(num/i): numbers.append(num/i)
        return numbers

i=10
numbers= []
while len(numbers) != 4:
        if len(getPrimeFactors(i)) == 4:
                numbers.append(i)
        if len(numbers) == 4:
                if not (numbers[0]+1 == numbers[1] and numbers[1]+1 == numbers[2] \
                        and numbers[2]+1 == numbers[3]):
                        numbers = [numbers[1],numbers[2],numbers[3]]
        i+=1

print (numbers)
run_time = time.time() - start_time
print (run_time)
Personal tools