どうも!LSSです!!
取り乱した時に、素数を数えて落ち着く神父さんの話がありますが、LSSは特に意味もなくなんとなく素数判定するスクリプトを書いてみました。
ここをクリックすると10000までの素数が出てきます(結構大量)
コード
<div id="gamen"> </div>
<script>// <![CDATA[
function sosuu(){
gamen.innerHTML='';
var cst=0;
var ss=[];
ss.push(2);
for(i=3;i<=10000;i+=2){
sh=true;
for(j=1;(ss[j]<=Math.sqrt(i)) && (j<ss.length) && sh;j++){
cst++;
if(i%ss[j]==0){sh=false;}
}
if(sh){ss.push(i);}
}
for(j=0;j<ss.length;j++){
gamen.innerHTML+=ss[j]+',';
}
gamen.innerHTML+="<br/>判定回数:"+ cst + " 素数の数:"+ ss.length;
}
// ]]></script>
最初の素数「2」は先に配列に入れておき、調査は3からスタート、調査対象となる数iは+=2する事で奇数だけを対象としています。
調査時のループは、「調査対象の平方根を超えない範囲」の「これまでに見つけた素数(2以外)」で割り切れるか否かを判定しています。
…と、自分に理解できるアルゴリズムのうちでは多分これが一番低コストですが、世の中には「もっと効率の良いアルゴリズムがある」との事。
ちなみにこの記事のスクリプトの場合、LSSのPCで
「10万まで調べようとすると数秒待たされる、100万まで調べようとするとブラウザが数回、待機するかどうか聞いてくる」
程度でした。
Wikipediaで調べていると、微分積分を習得できなかったレベルの自分には難易度の高い話がどっさりですw
「素数って何に使うの?」は、素数探索よりも難しい問題かも知れませんが、LSSの場合は「超巨大迷宮」の疑似乱数に使います^^
Wikiに「暗号鍵に使う」という例が載っていたのを見て、同じような事例だな、となんか安心しましたw
てなとこで、今回はこのへんで!
次回もまた、よろしくです^^