5問目

2520 は 1 から 10 までのそれぞれの数で割り切れる最小の数です.
では, 1 から 20 までの全ての数で割り切れる最小の数は何?

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

数学的にも簡単だし, アルゴリズム的にもすっきり書けるのであまり悩まなかったが, 出てきた答えが案外大きな数字で驚いた.
因みに Lisp で書くと,

(lcm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

シンプルで素晴しい.
Project Euler の2周目では, Lisp にしようかしら?それか, C での最小長プログラムに挑戦しようかしら?

3問目で使った prime 関数をここでも使っている.
今は

$ gcc Problem005.c ../../lib/prime.o -o Problem005

なんてやってるが, そのうちライブラリ化しておきたい.

/* Problem005.c */
#include <stdio.h>
#include <math.h>
#include <unistd.h>
#include <ctype.h>
#include "prime.h"

#define DEFAULT_NUMBER 20

long solveVer00(int);
long solveVer01(int);

int version;
int number;
int parseArg(int, char**);

long lcm(long, long);
long gcd(long, long);

int main(int argc, char **argv) {
	if (parseArg(argc, argv) == EXIT_FAILURE) {
		return EXIT_FAILURE;
	}
	switch (version) {
	case 0:
		fprintf(stdout, "Solution: %ld.\n", solveVer00(number));
		break;
	case 1:
		fprintf(stdout, "Solution: %ld.\n", solveVer01(number));
		break;
	default:
		break;
	}
	return EXIT_SUCCESS;
}

long solveVer00(int number) {
	int i;
	long result;

	result = 1;
	for (i = 1; i < number; i++) {
		result = lcm(result, i);
	}
	return result;
}

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

	result = 1;
	prime(20);
	while ((p = prime(0)) != -1) {
		power = (int) (log(number) / log(p));
		result *= pow(p, power);
	}
	return result;
}

long gcd(long num1, long num2) {
	long temp;

	while (num2 > 0) {
		temp = num1 % num2;
		num1 = num2;
		num2 = temp;
	}
	return num1;
}

long lcm(long num1, long num2) {
	return num1 * num2 / gcd(num1, num2);
}

int parseArg(int argc, char **argv) {
	int optChar;

	// default values
	version = 0;
	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 = atoi(argv[optind]);
	}	
	return EXIT_SUCCESS;
}

/* prime.h */
#ifndef __PRIME_H__
#define __PRIME_H__

#include <stdlib.h>
#include <stdio.h>

long long prime(long long);

#endif

/* prime.c */
#include "prime.h"

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;
	}
}