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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095
Problem 95 「友愛鎖」 †
約数の和に関する問題。

速度を求めればこのコード改善点はいくつかある。
例えば約数の和を求める部分が遅いけど気にするほどでもないのでわかりやすさ優先。

#include<stdio.h>
#include<set>

const int LIMIT=1000*1000;
int chain[LIMIT+1]={0};
int memo[LIMIT+1]={0};
struct E{
	int n,len;
	bool stop;
};

E saiki(int n,int seed,int len){
	E e1;
	if(memo[n]>LIMIT){
		e1.len=-1;
		return e1;
	}
	
	if(chain[n]==LIMIT){
		e1.len=-1;
		e1.stop=true;
		return e1;
	}

	
	if(chain[n]==0){
		chain[n]=len;
		e1=saiki(memo[n],seed,len+1);
		chain[n]=LIMIT;
		if((e1.stop==false)&&(e1.n>n)){
			e1.n=n;
		}
		if(e1.n==n)e1.stop=true;
		return e1;
	}else{
		e1.len=len-1;
		e1.n=n;
		e1.stop=false;
		return e1;
	}
	
}

int main(){
 	for(int i=1;i<=LIMIT;i++){
	for(int j=i*2;j<=LIMIT;j+=i){
			memo[j]+=i;
		}
	}
 	int ansLen=0,ansN=0,len;
for(int i=2;i<=LIMIT;i++){
 		if(chain[i]==0){
			E e1=saiki(i,i,1);
			if(e1.len>ansLen){
				ansLen=e1.len;
				ansN=e1.n;
			}
		}
 	}
	printf("ans=%d len=%d",ansN,ansLen);
}