Top / エラトステネスの篩を利用した方法
HTML convert time: 0.008 sec.

エラトステネスの篩を利用した方法

Last-modified: 2015-03-21 (土) 14:08:49

私がはじめて素因数分解のプログラムについて考えたときに思いついたのが、このエラトステネスの篩を使って√Xまでの素数を用意して割っていくという方法でした。素数生成の際にエラトステネスの篩の速さについて思い知らされたので、素因数分解する数が大きくなるにつれてエラトステネスの篩の篩を使った方がとても速くなると考えたからです。

しかし、このプログラムを書く際に大きな問題がありました。
それは配列の上限です。エラトステネスの篩では配列を利用して篩にかけます。2^64-1(64bitの最大値) の素因数分解には2の32乗個の配列が必要となります。しかし、用意できる配列の上限はおよそ4.5億個までのようで、64bitで扱えるのはおよそ900京までですが4.5億個の配列では20京までの数までしか素因数分解できないことになります。
限定的ですがとりあえずこの条件のままプログラムを書きたいと思います。

<ソースコード>

/*                         */
/*    Factorization.exe    */
/*                         */

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

#define N  447300000   // 用意する配列
#define PN 24000000    // 素数を入れる配列

int n[N+1];
int pn[PN];

int main()
{
	cout << sqrt(20) << endl;
	__int64 X;

	cout << "\n素因数分解" << endl;
	cout << "* MAX:200000000000000000 *" << endl;

	cout << "    X=";
	cin >> X;
	cout << "\n" << X << " = ";

	clock_t start = clock();

	for (int i = 3; i <= sqrt(X); i = i + 2){
		n[i] = i;
	}
	
	int pncount = 1;
	pn[1] = 2;
	pncount++;

	for (int i = 3; i <= sqrt(X); i = i + 2){
		if (n[i]){
			pn[pncount] = i;
			pncount++;
			for (int j = 3; i*j <= sqrt(X); j = j + 2){
				n[i*j] = 0;
			}
		}
	}	

	pncount--;

	__int64 quo = X;

	for (int i = 1; i <= pncount; i++){
		int sub = pn[i];
		if (quo%sub == 0){
			int ruijo = 0;
			cout << sub;
			while (quo%sub == 0){
				ruijo++;
				quo = quo / sub;
			}
			if (ruijo == 1){
				cout << " ";
			}
			if (ruijo >= 2){
				cout << "^" << ruijo << " ";
			}
			if (quo == 1){
				break;
			}
		}
	}

	if (quo > pn[pncount]){
		if (quo == X){
			cout << "Prime Number";
		}
		else{
			cout << quo ;
		}
	}
	cout << endl;

	clock_t end = clock();
	cout << "\ntime=" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;

	return 0;
}

<計算結果>

 X : time (総当たりで行ったときの時間)
 123456787654321 : 0.164s (0.001s)
 12345678987654321 : 1.998s (0.014s)
 100000000000000000 : 8.37s (0.001s)

よくよく考えてみると、素因数分解する数が大きく素因数が小さいときはエラトステネスの篩では余計な素数を大量に求めていることになるので計算時間が多くかかってしまいます。
しかし、数が大きく、その数を構成する素因数が大きい数ではエラトステネスの篩を使った方が速いのではないかと思いその数を探しました。

X : (総当たりでかかった時間) , (エラトステネスの篩でかかった時間)
876543212345678 : 0.425s : 0.476s
98765432123456789 : 7.173s : 8.102s
100000000000000003(素数) : 7.229s : 7.304s

さまざまな数を試しましたが、エラトステネスの篩の方で扱える範囲の数ではほとんど勝ち目がないようです。
次にのページではこれらの弱点を補い合ったプログラムを紹介します。