Euler Problem 77

So this one is simply a variant of the previous problem, but with the additional of a prime number filter. Its necessary to work backwards until you have a count that closest to 5000, without going under.

#Euler77
class Algorithms:
    def partitionsGen(self, n):
        ms = {n: 1}
        keys = [n]
        yield ms
        while keys != [1]:
            if keys[-1] == 1:
                del keys[-1]
                reuse = ms.pop(1)
            else:
                reuse = 0
            i = keys[-1]
            newcount = ms[i] = ms[i] - 1
            reuse += i
            if newcount == 0:
                del keys[-1], ms[i]
            i -= 1
            q, r = divmod(reuse, i)
            ms[i] = q
            keys.append(i)
            if r:
                ms[r] = 1
                keys.append(r)
            yield ms
    def primeGen (self, lowerLimit, upperLimit):
        isPrime = [False, True]
        i = 2
        while i < upperLimit:
            isPrime.append(True)
            i += 1
        p = 2
        while p * p < upperLimit:
            if isPrime[p] == True:
                m = p * p
                while m < upperLimit:
                    if m % p == 0:
                        isPrime[m] = False
                    m += p
            p += 1
        P = []
        count = 0
        for p in isPrime:
            if p and count >= lowerLimit :
                P.append(count)
            count += 1
        return P
class Problem77:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        answer = 0
        Primes = self.Euler.primeGen(2,self.limit+1)
        print Primes
        while answer == 0:
            count = 0
            print "Prime Partitioning "+str(self.limit)
            for part in self.Euler.partitionsGen(self.limit):
                flag = True
                for n in part:
                    if n not in Primes:
                        flag = False
                if flag == True:
                    count += 1
            print "Count = "+str(count)
            if count < 5000:
                answer = self.limit + 1
            self.limit -= 1
        return "Answer = " + str(answer)
if __name__ == '__main__':
    P = Problem77(73)
    print P.Solution()

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 )

Connecting to %s