Primitive Pythagorean Triples
Statement
Goal
In this problem, we are given an input integer N, and your goal is to find the number of all primitive Pythagorean triples up to and including N.A Pythagorean triple is a triple (a, b, c), where a, b and c are positive integers such that a² + b² = c². We want to find the number of all of these triples, such as
Input
Line 1: An integer N.
Output
Line 1: Number of all primitive Pythagorean triples up to and including N.
Constraints
0 < N ≤ 10⁶
Example
Input
1
Output
0
Tags
Mathematics, Number theory
Difficulty
Medium
Test cases
No Triples Test
Input
1
Output
0
No Triples - Validator Validator
Input
4
Output
0
Only One Test
Input
5
Output
1
Only One - Validator Validator
Input
10
Output
1
More Triples Test
Input
150
Output
24
More Triples - Validator Validator
Input
138
Output
21
Even More Triples Test
Input
1538
Output
247
Even More Triples - Validator Validator
Input
1789
Output
287
Huge Amount Test
Input
1000000
Output
159139
Huge Amount - Validator Validator
Input
965342
Output
153630
Solution language
Solution
Stub generator input