Top / 素数生成-比較
HTML convert time: 0.017 sec.

素数生成-比較

Last-modified: 2015-03-15 (日) 12:27:59

 紹介した2つの素数生成のプログラムを使用して速さを比べてみたいと思う。

<方法>
 ・素数を表示させると余計な時間がかかってしまうため、2からXまでの素数の数を調べるのにかかる時間を調べる。
 (素数生成のプログラムを少し変えると素数を数えるプログラムにできる)
 ・X は 100000000(10^8) とする。

  ちなみに答えは 5761455

<結果>
 ・試し割:102.082s
 ・エラトステネスの篩:1.312s

  エラトステネスの篩…とても速いです…

<ソースコード>

/*                     */
/*     素数生成 比較    */
/*                     */

#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;

#define X 100000000

int arr[X+1];

void nomal()
{
        cout << "試し割" << endl;
	cout << X << "までの素数" << endl;

	clock_t start = clock();

	int count = 0;

        count++;        // 2 について

	for (int i = 3; i <= X; i = i + 2){      // 奇数について
		int k = 0;

		for (int j = 1; j <= sqrt(i); j = j + 2){
			if (i%j == 0){
				k++;
			}
			if (k > 1){
				break;
			}
		}
		if (k == 1){
			count++;
		}
	}
	clock_t end = clock();
	cout << "time=" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
	cout << "素数の数:" << count << endl;
}

void erat()
{
	cout << "エラトステネスの篩" << endl;
	cout << X << "までの素数" << endl;

	clock_t start = clock();

	for (int i = 3; i <= X; i = i + 2){
		arr[i] = 1;
	}

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

	int count = 0;

	count++;          // 2 について

	for (int i = 3; i <= X ; i = i + 2){
		if (arr[i]){
			count++;
		}
	}

	clock_t end = clock();
	cout << "素数の数:" << count << endl;
	cout << "time=" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
}
 
int main()
{
        nomal();
        erat();

        return 0;
}