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

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

力づくの計算法で計算量36774はまあまあまかな。
数式を解析するともっと根本的な方法で出るらしい。

#include<stdio.h>
#include<math.h>

const int MAX=10000;
int memo[MAX]={0};
int main(){
	int count=0;
	int Down=sqrt(MAX);
 	for(int i=1;i*i<MAX;i++){
		for(int k=2;k*i<MAX;k++){
			int p=k*i;
			memo[p]+=i;
			count++;
			if(i<k&&i>1)memo[p]+=k;
 		}
	}
	int ans=0;
	for(int i=1;i<MAX;i++){
		int t=memo[i];
 		if(t!=i&&t<MAX&&i==memo[t]){
			ans+=i;
		}
		count++;
	}
	printf("ans=%d 計算量=%d\n",ans,count);
}