素数判定 in C/C++

エラトステネスの篩は以前に書いたのだが、このアルゴリズムはある1つの数が素数かどうかを判定するには向いていない。

今回は、試し割りによって数nの素数判定を行う関数bool is_prime(const unsigned n)を実装する。

#愚直な実装

bool is_prime(const unsigned n){
	switch(n) {
		case 0: // fall-through
		case 1: return false;
	} // n > 1 が保証された

	// n より小さい数で n を割って余りを調べる
	// 素数ならば自分より小さい数(1以外)では割り切れない
	for(unsigned i = 2; i < n; ++i) {
		if(n % i == 0) return false;
	}

	return true;
}

#「愚直な実装」の問題点
・2～n-1まで試し割りしているが、実は2～$\sqrt{n}$で十分
・奇数・偶数問わず試し割りしているが(2以外の)偶数は素数ではないので、実は奇数のみで試し割りすればよい。

#修正した実装

bool is_prime(const unsigned n){
	switch(n) {
		case 0: // fall-through
		case 1: return false;
		case 2: return true;
	} // n > 2 が保証された

	if(n % 2 == 0) return false;

	// 上で i=2 相当は調べたので、i=3から奇数のみ調べる
	for(unsigned i = 3; i * i <= n; i += 2) {
		if(n % i == 0) return false;
	}

	return true;
}

#より良い実装
3以上の素数は、6で割ったときの余りが1か5になる¹。
別の言い方をすると、3以上の素数は6の倍数の前後にのみ存在する。

bool is_prime(const unsigned n){
	switch(n){
		case 0: // fall-through
		case 1: return false;
		case 2: // fall-through
		case 3: return true;
	} // n > 3 が保証された

	if(n % 2 == 0 || n % 3 == 0) return false;
	// n は 2 と 3 のいずれの倍数でもないことが保証された
	// これより n は (6の倍数)-1 か (6の倍数)+1 である

	// 6の倍数前後の数を使って試し割りをする
	for(unsigned i = 5; i * i <= n; i += 6) {
		if(n % i     == 0) return false; // (6の倍数)-1
		if(n % (i+2) == 0) return false; // (6の倍数)+1
	}

	return true;
}

6は素数である2と3の積なのでこんなことができる。
次の素数である5を更にかけると30になるが、30で割った余りは役に立つようには思えない。
素数となる数の候補が多すぎるのだ。
$(30n+1,30n+7,30n+11,30n+13,30n+17,30n+19,30n+23,30n+29)$

1. 自然数 $n$ を用いて、任意の自然数は$6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5$のいずれかとして表現できる。このうち、$6n$は6の倍数、$6n+2, 6n+4$は2の倍数、$6n+3$は3の倍数なので、素数である可能性があるのは$6n+1, 6n+5$のみ ↩