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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2072
Problem 72 「分数の数え上げ」 †
１以下の分数で分母が２～１００万までの既約分数の個数を答えよ。

解法
分母が決まった時、その分母での既約分数の数はファイ関数で求まります。
後はファイ関数は掛け算のみで表現でき掛け算は掛ける順番を変えても答えが変わらないということを利用して。
素因数からファイ関数の掛け算の分母と分子を別々に求め、最後のループで一気に計算します。
実行時間0.1秒。
もっと早い方法もあるようですが私が思いついたのはこの程度です。

#include<stdio.h>
#include<iostream>
#include <time.h>

const int LIMIT=1000*1000;
__int64 divs[LIMIT+1]={0};
__int64 mults[LIMIT+1]={0};

int main(){
 	clock_t start,end;
  	start = clock();
	
__int64 ans=0;
	for(int i=2;i<=LIMIT;i+=1+(i&1)){
		if(divs[i]!=0)continue;
		for(int j=i*2;j<=LIMIT;j+=i){
			if(divs[j]==0){
				divs[j]=i;
				mults[j]=(i-1);
			}else{
				divs[j]*=i;
				mults[j]*=(i-1);
			}
		}
 	}
	for(int i=2;i<=LIMIT;i++){
		__int64 add;
		if(divs[i]==0){
			add=(i-1);
		}else{
			add=((i/divs[i])*mults[i]);
		}
		ans+=add;
 	}
	end = clock();
	
	std::cout<<"ans="<<ans<<"\ntime="<<end-start<<"ミリsec";
}