R:素数を。求める。~各務ゼミ生に送る~
こんにちは。チャパティです。
隣で彼女が海外サイトでクレジットカードが使えないって喚いてます。
僕もairasiaでタイ行きのフライトとるとき苦労したので、気持ちはよくわかる。
と、雑談はそこらへんにしておいて、
素数を求める。
今回のゼミの課題が、
Rを用いて素数を求める。出来る限り効率的に求める。コードは自力で書く。
という課題なので、この記事はまだ試行途中ではあります。
そもそも素数って?
素数(そすう、英: prime number)とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
wikiより
まぁ、1とその数でしか割り切れない数ってことです。
ちなみに、wikiでこの続きに
一般には、素数は代数体の整数環の素元として定義される(そこでは反数などの同伴なものも素数に含まれる)。このため、有理整数環Zでの素数は有理素数(ゆうりそすう、英: rational prime)と呼ばれることもある。
wikiより
って書いてあったんですが、何のことかさっぱりです。
素数をRで求める。
今回のプログラミングはザックリいうと
ある数kに対して1からkまで順番に割っていって、2回割り切れたらOK、そうじゃなかったら、ダメ
というものです。
では
コード
cN <- 10000
So <- NULL
for (i in 1:cN) {
k<-0
for (j in 1:i) {
if( i %% j == 0)
k <- k+1
}
if(k == 2)
So <- i
}
print(So)
やってること
cn=10,000
So=空白
k=0と条件設定
iを1からcnまで繰り返し①
jを1からiまで繰り返し②
i/jをしたときに余りが0ならkに+1する
繰り返し①終了
もしkが2ならSoにiを入れる
繰り返し②終了
Soを出力する
改良
「効率化しろ」という課題なので、
とりあえず、時間を計れるようにします。
入れるコードはこちら
Timer <- proc.time()
print(( proc.time() - Timer)[3])
proc.time()で時間を計れるのでこれをいれると
cN <- 10000
So <- NULL
Timer <- proc.time()
for (i in 1:cN) {
k<-0
for (j in 1:i) {
if( i %% j == 0)
k <- k+1
}
if(k == 2)
So <- i
}
print(( proc.time() -Timer)[3])
print(So)
になります。
でこれをコンパイル(が走らせるってことであってる?)すると
elapsed
8.33
で8.33秒になりました。
やべ、まぁまぁ長くなった。続きは後で書こ
まとめ
今日は素数書くプログラミングをしました。
次の改善パート1では
・割り切れる数はn/2以下でしか存在しない
・3回以上割り切れたら中断(K≧3になったらbreak)
について、書いていこうと思います。
それでは!
最後まで読んでくれてありがとう!読み終わって内容が面白ければ、「お疲れ様」の意味を込めて「缶コーヒー1杯飲める」程度のサポートをぜひ!