Euler Problem 73

Just use brute force to test the GCD for each iteration.

class Algorithms:
    def gcd(self, a, b):
        while b:
            a, b = b, a%b
        return a
class Problem73:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range(5, self.limit+1):
            for d in range(n/3 + 1, (n-1)/2 + 1):
                if self.Euler.gcd(n,d) == 1:
                    count += 1
            if n % 1000 == 0:
                print n, count
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem73(12000)
    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