プロジェクトオイラー問75 - sinapusu2002 @ ウィキ

Problem 75 「1通りの整数直角三角形」 †
長さLの鉄線を整数比に折って直角三角形を作るとき一通りの折り曲げ方しかできない長さの個数を数えよ。
ただしL<=150万とする。

解法
原始ピタゴラス数の公式とその定数倍を全探索して数えるだけです。

#include<stdio.h>

int gcd(int a,int b){
	while(a>0){
		int c=a;
		a=b%a;
		b=c;
	}
	return b;
}

const int LIMIT=1500*1000;
int count[LIMIT+1]={0};
int main(){
 	for(int m=2;2*m*(m+1)<=LIMIT;m++){
		for(int n=1+m%2;(n<m) && (2*m*(m+n)<=LIMIT);n+=2){
			if(gcd(m,n)!=1)continue;
			int len=2*m*(m+n);
			for(int k=len;k<=LIMIT;k+=len){
				count[k]++;
			}
 		}
	}
	int ans=0;
	for(int i=12;i<=LIMIT;i++){
		ans+=(count[i]==1);
	}
	printf("%d",ans);
}