21問目

を真の約数( の約数のうち より真に小さいもの)の合計と定義する.
もし かつ であり の場合, と を友愛数と呼ぶ.

例えば, 220 の真の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので . 284 の真の約数は 1, 2, 4, 71, 142 なので .

10000 未満の全ての友愛数の合計を求めよ.

http://projecteuler.net/index.php?section=problems&id=21

友愛数っていうのは, 代数学やってた身としては親しみのある数学の対象なのですが, 如何せん「約数を足す」という掛け算に関わる数字を足す操作をしてしまうため, なんとも扱いづらい数字なのです. 問題の理解のしやすさと解決の難しさの乖離という点では, 14問目の Collatz の問題と似た感じです.

このプログラムでもバリバリ素数を使っているので, やっぱり自作の prime 関数を使っています. prime 関数の実装が見たい人は過去の日記などを探してください. そのうちホームページの方にも載せます.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "prime.h"

int sumOfDivisors(int);
int sumOfProperDivisors(int);
int solveVer00(int);

int main(int argc, char **argv) {
	int upperBound;

	if (argc < 2) {
		fprintf(stderr, "Error: too few argument.\n"
				"a value of upper bound is needed.\n");
		return EXIT_FAILURE;
	}

	upperBound = atoi(argv[1]);
	fprintf(stdout, "Solution: %d.\n", solveVer00(upperBound));

	return EXIT_SUCCESS;
}

int solveVer00(int upperBound) {
	int number;
	int companion;
	int result;

	initPrime();
	for (number = 2, result = 0; number < upperBound; number++) {
		companion = sumOfProperDivisors(number);
		if (number != companion
			&& number == sumOfProperDivisors(companion)) {
			result += number;
//			fprintf(stdout, "%d, %d\n", number, companion);
		}
	}

	return result;
}

int sumOfProperDivisors(int number) {
	return sumOfDivisors(number) - number;
}

int sumOfDivisors(int number) {
	long long p;
	int power;
	int result;

	prime(-1);
	result = 1;
	while (number > 1
		   && (p = prime(0)) != -1) {
		power = 0;
		while ((number % p) == 0) {
			number /= p;
			power++;
		}
		result *= (pow(p, power + 1) - 1) / (p - 1);
	}

	return result;
}