素数を求める[エラトステネスのふるい][JavaScript]

素数とは、2以上の整数で1とその数自身でしか割りきれない数のことを言う。今回は1000以下のすべての素数を見つけるためのアルゴリズムをJavaScriptで実装してみた。

まずはもっとも単純で分かりやすい方法から記述しておく。

function getPrime(){
	let n,i;
	const num = 1000;
	
	for(n=2; n<=num; n++){
		for(i=2; i<n; i++){
			if(n%i==0) 
				break;
			}
		if(n==i)
			console.log(n);
	}
	
}

getPrime();

function getPrime(){

let n,i;

const num = 1000;

for(n=2; n<=num; n++){

for(i=2; i<n; i++){

if(n%i==0)

break;

}

if(n==i)

console.log(n);

}

getPrime();

次に「エラトステネスのふるい」と呼ばれる解法で記述してみる。エラトステネスは3世紀古代ギリシャの科学者である。エラトステネスのふるいとは、ある数の平方根よりも小さい素数の倍数を消していけばその数までの素数だけが残る、という手法に基づいている。このアルゴリズムは以下のような流れで実装することができる。

・探索範囲（2〜N）の全整数を用意する。
・Nの平方根以下の素数の倍数をその全整数から取り除いていく。
・残った数を出力する。

N=20までの数の素数を、具体的な手順で求めていく。

2,3,4,5,6,7,8,9,10
11,12,13,14,15,16,17,18,19,20

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

まず最小の素数である2の倍数を消していく（2はそのまま残し、倍数は素数ではないので取り除く）。

2,3,5,7,9
11,13,15,17,19

1 2	2,3,5,7,9 11,13,15,17,19

次に、2の次に大きい素数である3の倍数を消していく。

2,3,5,7
11,13,17,19

1 2	2,3,5,7 11,13,17,19

3の次に大きい素数は5である。5はそれ以下の数で割り切れなかったということで素数である。しかし、5は20の平方根よりも大きいので、残りの数に対してもう操作は行わない。以上の操作によって残った数が、20までの数の素数である。

平方根以下の素数の倍数までという理由は、例えばN=a*bの場合、a>√Nだとするとb<√Nとなるので、つまり√Nより小さい値で割り切れるかの判定はすでにしているからということになる。上記の例で言えば、5*2、5*3はすでに取り除いているし、5*5は20を超えてしまうので、5以上の素数はもう考えなくても良いということになる。

以下エラトステネスのふるいによって1000以下の素数を求める関数。

function getPrime(){
	let primes = [];
	let i,j;
	const num = 1000;
	
	for(i=2; i<=num; i++)
		primes[i] = true;
	
	for(i=2; i<=Math.sqrt(num); i++){
		if(primes[i] === true){
			for(j = i*2; j<=num; j+=i)
				primes[j] = false;
		}
	}
	
	for(i=2; i<=num; i++){
		if(primes[i] === true){
			console.log(i);
		}
	}
	
}

getPrime();

function getPrime(){

let primes = [];

let i,j;

const num = 1000;

for(i=2; i<=num; i++)

primes[i] = true;

for(i=2; i<=Math.sqrt(num); i++){

if(primes[i] === true){

for(j = i*2; j<=num; j+=i)

primes[j] = false;

}

for(i=2; i<=num; i++){

if(primes[i] === true){

console.log(i);

}

getPrime();

Pocket

思考の葉

思考の葉

素数を求める[エラトステネスのふるい][JavaScript]