JavaScriptで整数問題を記述するAPIを改良:素数未満の素数の個数が素数であるような場合を求めよ


ある素数について,それより小さい素数の個数が素数個であるような場合を求めるコード。 ====

<input type="button" value="計算開始" onclick="calc()"><br>

<textarea id="d" cols="80" rows="20"></textarea>


<script>

function calc(){
	clear_log();

	// 素数を見つけよ
	find_all_primes_that( function( N ){ return (
		
		// この条件を満たすものを
		
		// N未満の素数の個数(素数計数関数)の値が
		prime_counting_function( N - 1 )
		
			// 素数であること
			.isPrime()
		
	);})
	
	// 結果を表示せよ
	.display()
	;

}



// 以下ライブラリ


// 探索範囲の上限
var TESTING_LIMIT = 10000


// ある素数を見つけよ(満たすべき条件は関数で渡す)
function find_all_primes_that( func ){
	return (
		new IntArr()
			.generate_primes( 1, TESTING_LIMIT )
			.filter( func )
	);
}


// 整数の配列のラッパ
var IntArr = function(){};
IntArr.prototype = {
	
	// 配列を内部に保持
	_arr : [],
	
	item : function( i ){
		return this._arr[ i ];
	},

	// ステップ刻みで配列を生成
	generate_by_step : function( i_start, i_end, i_step ){
		this._arr = [];
		for( var i = i_start; i <= i_end; i += i_step ){
			this._arr.push( i );
		}
		return this;
	},
	
	// ある範囲内で素数列を生成
	generate_primes : function( i_from, i_to ){
		return this.generate_by_step( i_from, i_to, 1 )
			.filter(function(n){
				return n.isPrime();
			})
			//.display()
		;
	},
	
	// 条件で絞込み
	filter : function( func ){
		this._arr = this._arr.filter( func );
		return this;
	},
	
	// 保持している配列の内容を表示
	display : function(){
		var tmp = [];
		for( var i = 0; i < this._arr.length; i++ ){
			tmp.push( /* i + ":" + */ this.item( i ) );
		}
		log( "[ " + tmp.join(", ") + " ]" );
		
		return this;
	}

};


// 素数判定
Number.prototype.isPrime = function(){
	// できるだけキャッシュから回答する
	return PrimeCache.judge( this );
};
// 素数判定結果のキャッシュ
var PrimeCache = {
	_arr : [],
	
	// キャッシュ利用可で判定せよ
	judge : function( num ){
		if(
			( this._arr.length >= num )
			&&
			( this._arr[ num - 1 ] != null )
		){
			//log("cache hit : " + num);
		
			// キャッシュから回答
			return this._arr[ num - 1 ];
		}else
		if( this._arr.length < num ){
			//log("too short : " + num);
			
			for( var i = this._arr.length; i < num - 1; i ++ ){
				this._arr.push( null ); // まだ計算しないでおく
			}
			
			var b = this.calc_is_prime( num );
			this._arr.push( b );
			return b;
		}else
		//if( this._arr[ num - 1 ] == null )
		{
			//log("delayed : " + num);
			
			var b = this.calc_is_prime( num );
			this._arr[ num - 1 ] = b;
			return b;
			
		}
	},
	
	// キャッシュを使わずに判定
	calc_is_prime : function( num ){
		if( num < 2 ) return false;
	
		var m = Math.floor( num / 2 );
		for( var i = 2; i <= m; i ++ ){
			if( num % i == 0 ){
				//log("not prime : " + num);
				return false;
			}
		}
		//log("is prime : " + num);
		return true;
	}
};


// 素数計数関数
function prime_counting_function( n ){
	// ダブリ処理をなくすためにキャッシュから回答
	return PrimeCountingCache.how_many( n );
}
var PrimeCountingCache = {
	_arr : [],
	
	// いくつか?(キャッシュ利用可で答えよ)
	how_many : function( num ){
		if(
			( this._arr.length >= num )
			&&
			( this._arr[ num - 1 ] != null )
		){
			// キャッシュから回答
			return this._arr[ num - 1 ];
		}else
		if( this._arr.length < num ){
			for( var i = this._arr.length; i < num - 1; i ++ ){
				this._arr.push( null ); // まだ計算しないでおく
			}
			
			var n = this.calc_prime_counting( num );
			this._arr.push( n );
			return n;
		}else
		//if( this._arr[ num - 1 ] == null )
		{
			var n = this.calc_prime_counting( num );
			this._arr[ num - 1 ] = n;
			return n;
			
		}
	},
	
	// キャッシュを使わずに回答せよ
	calc_prime_counting : function( num ){
			//log( num );
		if( num == 1 ) return 0;
		return this.how_many( num - 1 )
			+ ( num.isPrime() ? 1 : 0 )
		;
	}
};


// 配列中で条件にマッチするものだけを残す
Array.prototype.filter = function( func ){
	var new_arr = [];
	this.each(function(){
		if( func( this ) ){
			new_arr.push( this );
		}
	});
	return new_arr;
};

// イテレータ
Array.prototype.each = function( func ){
	for( var i = 0; i < this.length; i ++ ){
		func.call( this[ i ], i );
	}
};


// 結果表示用

function log( s ){
	$("d").value = s + "\n" + $("d").value;
}

function clear_log( s ){
	$("d").value = "";
}


function $( dom_id ){
	return document.getElementById( dom_id );
}


</script>

実行結果:

[ 5, 7, 13, 19, 37, 43, 61, 71, 89, 113, 131, 163, 181, 193, 223, 251, 281, 293, 337, 359, 373, 409, 433, 463, 521, 557, 569, 593, 601, 619, 719, 743, 787, 809, 863, 881, 929, 971, 997, 1033, 1069, 1091, 1163, 1181, 1213, 1223, 1301, 1423, 1439, 1451, 1481, 1511, 1531, 1601, 1627, 1693, 1733, 1747, 1789, 1831, 1861, 1931, 2029, 2069, 2083, 2111, 2237, 2273, 2347, 2357, 2383, 2423, 2503, 2551, 2617, 2657, 2687, 2729, 2753, 2819, 2903, 2917, 3011, 3023, 3079, 3119, 3181, 3251, 3271, 3301, 3323, 3413, 3491, 3527, 3571, 3607, 3643, 3739, 3767, 3917, 3947, 4049, 4093, 4139, 4157, 4219, 4283, 4349, 4409, 4423, 4481, 4519, 4561, 4583, 4673, 4783, 4789, 4813, 4889, 4937, 4951, 5023, 5077, 5113, 5197, 5297, 5387, 5443, 5507, 5563, 5639, 5653, 5711, 5779, 5807, 5857, 5879, 6043, 6121, 6221, 6247, 6317, 6329, 6359, 6367, 6473, 6607, 6659, 6673, 6701, 6827, 6857, 6869, 6907, 7069, 7121, 7207, 7297, 7369, 7433, 7487, 7529, 7621, 7669, 7703, 7757, 7853, 7901, 8017, 8069, 8111, 8123, 8231, 8237, 8291, 8387, 8419, 8521, 8537, 8597, 8731, 8753, 8779, 8819, 8861, 8929, 9001, 9043, 9109, 9311, 9323, 9413, 9463, 9547, 9623, 9677, 9743, 9839, 9871, 9929 ]

下記のライブラリを改良した。

整数問題を解くJSコード: 2^n−1が31で割り切れるようなケースを列挙する - ソフトウェア勉強ログとサンプルコード
http://source-code-student.hatenablog.jp/entry/20141221/p1


工夫した所:

  • 素数判定や,素数計数関数の値をキャッシュしておき,速度向上を図った。
  • メインの条件部分をシンプルに記述できているのが良いと思う。


今後の課題:

  • 探索範囲が大きくなるとブラウザが固まるので,ループ処理の非同期化と上手く組み合わせたい。
  • Numberそのものに素数判定メソッドを組み込んだのは良い案だった。さらにRuby的に,(1).to(100)みたいに書けるようにprototype.jsを部分的に参考にしたら便利かも。