Euler Problem 87 – More Primes

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