ProjectEuler/21-30

Last-modified: 2013-11-06 (水) 17:50:33

21

約数の和を記録

(ある数の約数の和) < (ある数) だった場合に友愛数かどうかチェックすると重複しない。

#include
#include

using namespace std;

const int N_MAX = 10000;

vector<int> y(N_MAX);

int main(){
	int ans=0;
	for(int i=2;i<N_MAX;i++){
		y[i]=1;
		for(int k=2;k*k<=i;k++){
			if(i%k==0){
				y[i]+=k;
				if(k*k!=i) y[i]+=(i/k);
			}
		}
		if(y[i]<i && y[y[i]]==i){ ans+=(y[i]+i); }
	}
	cout << ans << endl;
	return 0;
}