素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

エラトステネスの篩

エラトステネスの篩 - Wikipediaを参考に。

function primeNumber(n){
	var r=[],s=[],tmp;
	for(var i=2;i<=n;r.push(i++));

	do{
		s.push(tmp=r.shift());
		r=r.filter(function(i)i%tmp);
	}while(r[r.length-1]>tmp*tmp);
	
	return s.concat(r);
}

primeNumber(20);//[2, 3, 5, 7, 11, 13, 17, 19]