Project Euler – Problem # 47 – Solved with Python

Problem:

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 = 22 * 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?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32
# stop_time =  6.33370859353 (seconds)

import sympy
import time
    
def get_factors(n):
    """Factor number n"""
    f = sympy.factorint(n)
    return f
        
def main():
    """Main Program"""
    start_time = time.clock()
    counter = 0
    for n in range(1000, 1000000):
        if counter == 4:
            print "Answer=", n - 4
            break
        else:
            x = get_factors(n)
            if len(x) == 4:
                counter += 1
            else:
                counter = 0
    stop_time = time.clock() - start_time
    print "stop_time = ", stop_time
    
if __name__ == '__main__':
    main()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s