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

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

### Like this:

Like Loading...

*Related*