Euler Problem 75

This one is just an extension of Problem 9. Fortunately I’m using Python now and there are really efficient list manipulation routines like [0]* and .count(x). Runs pretty fast.

import math
class Algorithms:
    def gcd(self, a, b):
        while b:
            a, b = b, a % b
        return a
class Problem75:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        S = [0]*self.limit
        for a in range(1, int(math.sqrt(self.limit)), 2):
            for b in range(2, int(math.sqrt(self.limit)), 2):
                if self.Euler.gcd(a, b) == 1: 
                    sum = int(math.fabs(b*b - a*a)) + 2*a*b + a*a + b*b
                    for s in range(sum, self.limit, sum):
                        S[s] += 1
        return "Answer = "+str(S.count(1))
if __name__ == '__main__':
    P = Problem75(1500000)
    print P.Solution()

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s