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