Problem 87

Comments

There were a couple of problems with this one that I needed to overcome. I wrote a good code that ran really fast, yet over and over came up with the same wrong answer. I think realized that it was because I was counting some numbers multiple times. Once I finally figured out the issue, I then came across the need to optimize the process. I was using a list before, but through digging around on the Python site I thought of using sets instead because they have good union, intersection, etc functions. Making that switch worked really well. This script ran in under 4 seconds.

Code

def isprime(n):
	if n == 0 or n == 1: return False
	for i in range(2, int(n**0.5 + 1)):
		if n%i == 0: return False
	return True

primes = []
n = 1
while n**2 < 5*10**7:
	n += 1
	if isprime(n) == True:
		primes.append(n)

belowset = set()
for square in primes:
	if square**2 > 5*10**7:
		break
	for cube in primes:
		if cube**3 > 5*10**7:
			break
		for tesseract in primes:
			if tesseract**4 > 5*10**7:
				break
			below = square**2 + cube**3 + tesseract**4
			if below < 5*10**7:
				belowset |= {below}
				
print len(belowset)