p075.py 956 Bytes
 Nayuki Minase committed Feb 19, 2016 1 2 ``````# # Solution to Project Euler problem 75 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` Nayuki Minase committed Feb 19, 2016 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ``````# # https://www.nayuki.io/page/project-euler-solutions # https://github.com/nayuki/Project-Euler-solutions # import eulerlib, fractions def compute(): LIMIT = 1500000 # # Pythagorean triples theorem: # Every primitive Pythagorean triple with a odd and b even can be expressed as # a = st, b = (s^2-t^2)/2, c = (s^2+t^2)/2, where s > t > 0 are coprime odd integers. # triples = set() for s in range(3, eulerlib.sqrt(LIMIT) + 1, 2): for t in range(s - 2, 0, -2): if fractions.gcd(s, t) == 1: a = s * t b = (s * s - t * t) // 2 c = (s * s + t * t) // 2 if a + b + c <= LIMIT: triples.add((a, b, c)) ways = [0] * (LIMIT + 1) for triple in triples: sigma = sum(triple) for i in range(sigma, len(ways), sigma): ways[i] += 1 `````` Nayuki committed Nov 03, 2016 35 `````` ans = ways.count(1) `````` Nayuki Minase committed Feb 19, 2016 36 37 38 39 40 `````` return str(ans) if __name__ == "__main__": print(compute())``````