Coder_Shubham_24's blog

Can anyone tell me the proof of Primitive Pythagorean Triples(a,b,c) having gcd(a,b,c)=1
By Coder_Shubham_24, history, 3 years ago, In English

I was solving this question Pythagorean Theorem II

and saw some optimized solution based on this relation seems

Saw some solved optimized codes using this relations seems gcd(a,b,c)=1

int n,m=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;(i*i+j*j<=n&&i>j);j++)
		{
			if((i-j)%2==1)
				if(gcd(i,j)==1)
					m+=n/(i*i+j*j);
		}
	}
	cout<<m;

I know a,b,c are relatively prime but is it enough to know that ?

Can somebody tell me proof of this approach ?

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

https://en.wikipedia.org/wiki/Pythagorean_triple

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the code you posted uses the fact that if a^2+b^2 = c^2, then k*a^2 + k*b^2 = k*c^2 for every positive integer k, so you only need to check the triples that have a gcd of 1 and count every multiple of those numbers until they become greater than n (which can be done in O(1) by dividing n by the biggest number).

→ Reply