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()

### Like this:

Like Loading...

*Related*