p077.py

# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:56:54 2013

@author: guillermo
"""
def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2:
        return True
    # all other even numbers are not primes
    if not n & 1:
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

scope = 4000
primes = []
for i in range(2, 7000):
    if isprime(i):
        primes.append(i)
ways = [1]+[0]*scope
 
for prime in primes:
    for i in range(prime, scope+1):
        ways[i] += ways[i-prime]

for i in range(0, len(ways)):
    if ways[i] > 5000:
        print i
        break
    
'''similar to problem 76, we do the same count technique in dynamic programming, but with a list of primes now'''