I started this one by iterating 50 million times. The code worked but it was damn slow. I figured it would take 27 hours. Not good. Then … lightbulb! Flip the question over by iterating on only the possible primes. Simple, elegant, fast — works in 4 seconds.

```
```#Euler87
import math
class Problem:
def primeGen (self, lowerLimit, upperLimit):
isPrime = [False] + [True]*(upperLimit-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
def Solution(self):
P2 = self.primeGen(2,int(math.exp(.5*math.log(50e6))))
P3 = self.primeGen(2,int(math.exp(math.log(50e6)/3)))
P4 = self.primeGen(2,int(math.exp(.25*math.log(50e6))))
print "Number of Primes for ", "2^:", len(P2), "3^:", len(P3), "4^:", len(P4)
N = []
for p2 in P2:
for p3 in P3:
for p4 in P4:
if p2**2 + p3**3 + p4**4 <= 50e6:
N.append(p2**2 + p3**3 + p4**4)
print "\nAnswer =", len(set(N))
if __name__ == '__main__':
P = Problem()
P.Solution()