素数

はじめに

学校で出された課題がきっかけになって，色々と調べた事をまとめてみました．
このページの内容をレポートなどに書く際は，参考文献としてここへのリンクを貼ってくれたら喜びます．

役に立つ原理

• 素数の集合をP，A={2, 3, 5, 6k+1, 6k+5 (kは正整数)}とするとP⊂A
• 集合Aで一番小さい素数でない数は25(=6*4+1)

エラトステネスのふるいを用いたPrimeクラス

概要

標準ライブラリしか使ってない，エラトステネスのふるいで実装したシングルトンなPrimeクラスです．
unsigned intの範囲内の自然数なら超高速で素数判定します．
疑素数やカーマイケル数でも全く問題ありません．

お役立ちな原理

• 自然数nをふるいにかける際は2から(int)sqrt((float)n)の間にある素数で割って一度も割り切れなかったらnは素数

ささやかな工夫

• 自然数nが素数かどうか記録した素数テーブルをstd::bitsetで実装
  • nビット目は素数なら1，素数でないなら0が登録されます
• インスタンスが生成された時点でn=65535までの素数テーブルを作ります
• これで4294836224くらいまでの数なら一瞬で素数判定できますね！

なんでstd::bitset使ったの？

正直，bool型の配列でも全くかまいません．
けど，std::bitsetの方が各演算子や any(), count(), to_stringなどが使えて便利です．

ソースコード

Prime.h

// Author : usi3
// http://usi3.com/
 
#include <bitset>
#include <cmath>
using namespace std;
 
#define N 65535
 
class Prime{
private:
	Prime(void){}
	Prime(Prime*);
	static Prime *pInstance;
	// nビット目にnが素数かどうかが記録される2進数のテーブル
	bitset<N> table;
 
public:
	static Prime* getInstance(void){
		if(!pInstance){
			// インスタンス生成
			pInstance = new Prime;
			pInstance->init();
		}
		return pInstance;
	}
 
	void init(){
		// 集合Aを素数候補としてとりあえず登録
		table.set(2);
		table.set(3);
		table.set(5);
		for(int i=1; i<(N-1-(N-1)%6)/6; i++){
			table.set(6*i+1);
		}
		for(int i=1; i<(N-5-(N-5)%6)/6; i++){
			table.set(6*i+5);
		}
		// 候補のみをエラトステネスのふるいにかける
		for(int i=25; i<N; i++){
			if(table.at(i)){
				if(!eratos(i)) table.reset(i);
			}
		}
	}
 
	// エラトステネスのふるい
	bool eratos(unsigned int p){
		int r = sqrt((float)p);
		for(int i=2; i<=r; i++){
			if(table.at(i)){
				if(p%i == 0) return false;
			}
		}
		return true;
	}
 
	// 整形して素数一覧を出力
	void view(unsigned int n){
		for(int i=0, c=0; i<n; i++){
			if(is(i)){
				printf("%5u ",i);
				if((++c)%10 == 0) cout << endl;
			}
		}
		cout << endl;
	}
 
	// 素数判定
	bool is(unsigned int n){
		if(n < N){
			return table.at(n);
		}else if(n < N*N){
			return eratos(n);
		}
	}
 
};
 
Prime* Prime::pInstance = 0;
}
}

使用例

main.cpp

#include <iostream>
#include "Prime.h"
using namespace std;
 
int main(void){
	Prime* p = Prime::getInstance();
 
	// 100以下の素数を整形して表示
	p->view(100);
 
	// 疑素数
	cout << p->is(1905) << endl;
	cout << p->is(8911) << endl;
 
	// カーマイケル数
	cout << p->is(561) << endl;
	cout << p->is(6601) << endl;
 
	// unsigned int 範囲内の大きな素数
	cout << p->is(1024760591) << endl;
	cout << p->is(1046028437) << endl;
	cout << p->is(2330842469) << endl;
	cout << p->is(2988897073) << endl;
	cout << p->is(3118688711) << endl;
	cout << p->is(3938292019) << endl;
	cout << p->is(4148217329) << endl;
 
	return 0;
}

おわりに

• エラトステネスのふるいじゃ300桁の自然数を素数判定しようと思ったら全く歯が立ちません
  • 疑素数とかでも問題がないMiller-Rabinテストがおすすめです！