I’m working on Project Euler problems, currently on problem 127. I manage to get the correct answer but my code takes nearly two and a half minutes. Ideally I would like it to run in under a minute, if possible.

My code:

import math

def problem_one_hundred_and_twenty_seven() -> int:
   answer = 0
   limit = 120000
   # limit = 1000

   # Modified sieve of Eratosthenes
   rad = [0] + [1] * limit
   for i in range(2, len(rad)):
      if rad[i] == 1:
          for j in range(i, len(rad), i):
              rad[j] *= i

   for c in range(limit):
      for a in range(1, c // 2):
        if rad[a] * rad[c] >= c:
            continue
        b = c - a
        if b <= a:
            continue
        if (
                # If gcd(a, b) = 1 then gcd(c,b) = gcd(a+b,b) = gcd(a,b) = gcd(a,a+b) = gcd(a,c) = 1.
                # If a, b, c are all co-prime then rad(a * b * c) = rad(a) * rad(b) * rad(c).
                # If gcd(a, b) != 1 then they share a prime factor, => gcd(rad(a), rad(b)) != 1.
                # so gcd(rad(a), rad(b)) = 1 => gcd(a, b) = 1
                math.gcd(a, b) == 1 and
                rad[a] * rad[b] * rad[c] < c
        ):
            # print(a, b, c)
            answer += c

    return answer


if __name__ == "__main__":
    start_time = time.time()
    print(problem_one_hundred_and_twenty_seven())
    end_time = time.time()
    print(f"Found in {end_time - start_time} seconds")