Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.