Count Pythagorean Triplets
hardMath & Number Theory+40 XPTime limit 2s
A carpenter only cuts right-angled triangles with whole-number sides. Count the Pythagorean triplets (a, b, c) with a < b < c ≤ n and a² + b² = c². For n = 15 there are 4: (3, 4, 5), (6, 8, 10), (5, 12, 13) and (9, 12, 15).
Input: one integer n.
Output: the number of triplets with all sides at most n.
Constraints: 1 ≤ n ≤ 10⁶. (Trying every pair a, b is about 10¹² checks — far too slow.)
Think about it: every primitive triplet (sides with no common factor) comes from Euclid's formula: a = m² − k², b = 2mk, c = m² + k² with m > k ≥ 1, gcd(m, k) = 1 and m − k odd — each exactly once. Every other triplet is a primitive one scaled by t, so a primitive triplet with hypotenuse c contributes ⌊n / c⌋ triplets. m only goes up to about √n.
Sample input 1
15
Sample output 1
4
Sample input 2
5
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).