3問目

13195 の素因数は 5 と 7 と 13 と 29.
では, 600851475143 の素因数の中で最大のものは?

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

この問題の肝は「素数生成」なので prime という関数を用意し, prime(0) と呼び出すことで素数を次々と返していくようにした. 取得したい素数の上限は, 正の整数を引数に与えることで設定できる. アルゴリズムは「エラトステネスの篩(ふるい)」を使っている.
なので, 初期化の際にフラグの状態を記録する配列を malloc して用意しているのだが, 600851475143 を引数に与えてしまうとメモリが足らない……. そこで, を引数に渡している.

上記の仕様で作った解が solveVer01 関数なのだが(名前が安直なのは棚に上げておいて), メモリをかなり食っていて, もっと大きな整数にはいつか対応できなくなる. そこで, 単純に割り切れるかのチェックを 2 から順番に「全ての正の整数」で行う solveVer00 関数を作ってみたところ, 体感速度はほとんど変わらなかった. 経過時間を計測してみても10^-6 秒未満で, たとえ時間差があったとしても, 人間にとってあまり意味の無いレベルの時間差だった.
う〜ん, 安直な答えの方が良い結果になるとは……. 数学で使う数値計算のようなオーダーの計算量の計算をやっていた経験がバイアスになったか……. 良い経験になった.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <ctype.h>
#include <math.h>
#include <time.h>

#define DEFAULT_NUMBER 600851475143LL

long long solveVer00(long long);
long long solveVer01(long long);
long long prime(long long);

int main(int argc, char **argv) {
	int version;
	int optChar;
	long long number;
#ifdef TIME
	time_t start, end;
#endif

#ifdef TIME
	start = time(NULL);
#endif
	version = 0; // default value
	while ((optChar = getopt(argc, argv, "v:")) != -1) {
		switch (optChar) {
		case 'v':
			version = atoi(optarg);
			break;
		case '?':
			if (optopt == 'c') {
				fprintf(stderr, "Option -%c requires an argument.\n", optopt);
			} else if (isprint(optopt)) {
				fprintf(stderr, "Unknown option `-%c'.\n", optopt);
			} else {
				fprintf(stderr, "Unknown option character `\\x%x'.\n", optopt);
			}
			return EXIT_FAILURE;
		default:
			abort();
		}
	}
	if (optind == argc) {
		number = DEFAULT_NUMBER;
	} else {
		number = atoll(argv[optind]);
	}

	switch (version) {
	case 0:
		fprintf(stdout, "Solution: %lld.\n", solveVer00(number));
		break;
	case 1:
		fprintf(stdout, "Solution: %lld.\n", solveVer01(number));
		break;
	default:
		fprintf(stderr, "There is no solution of ver%d.\n", version);
		break;
	}
#ifdef TIME
		end = time(NULL);
		fprintf(stdout, "Elapsed time: %f.\n", difftime(start, end));
#endif

	return EXIT_SUCCESS;
}

long long prime(long long value) {
	static long long maxValue;
	static long long currentPrime;
	static int *primes;
	long long i;

	if (value > 0) { // reset
		maxValue = value;
		currentPrime = 1;

		if (primes != NULL) {
			free(primes);
		}
		if ((primes = malloc(sizeof(int) * maxValue)) == NULL) {
			fprintf(stderr, "Error: failed to malloc.\n");
			exit(EXIT_FAILURE);
		}
		/*
		 * 0: not prime
		 * 1: prime
		 */
		primes[0] = 0;
		primes[1] = 0;
		for (i = 2; i < maxValue; i++) {
			primes[i] = 1;
		}
		return 0;
	} else { // return next prime
		// search next prime number
		currentPrime++;
		while (currentPrime < maxValue
			   && primes[currentPrime] == 0) {
			currentPrime++;
		}
		if (currentPrime == maxValue) {
			return -1;
		}
		// get prime flags down
		for (i = currentPrime * 2; i < maxValue; i += currentPrime) {
			primes[i] = 0;
		}
		return currentPrime;
	}
}

long long solveVer00(long long number) {
	long long factor;

	factor = 1;
	while (number > 1) {
		factor++;
		while ((number % factor) == 0) {
			number /= factor;
		}
	}
	return factor;
}

long long solveVer01(long long number) {
	long long factor;
	long long maxFactor;

	prime(sqrt(number));
	
	while ((factor = prime(0)) != -1
		   && factor < sqrt(number)) {
		while ((number % factor) == 0) {
			number /= factor;
			maxFactor = factor;
		}
	}
	return (number == 1 ? maxFactor : number);
}