R:素数を。求める。～各務ゼミ生に送る～

こんにちは。チャパティです。

隣で彼女が海外サイトでクレジットカードが使えないって喚いてます。

僕もairasiaでタイ行きのフライトとるとき苦労したので、気持ちはよくわかる。

と、雑談はそこらへんにしておいて、

素数を求める。

今回のゼミの課題が、

Rを用いて素数を求める。出来る限り効率的に求める。コードは自力で書く。

という課題なので、この記事はまだ試行途中ではあります。

そもそも素数って？

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
wikiより

まぁ、１とその数でしか割り切れない数ってことです。

ちなみに、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＝０と条件設定
iを1からcnまで繰り返し①
jを1からiまで繰り返し②
i/jをしたときに余りが0ならkに＋１する
繰り返し①終了
もしkが２なら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≧３になったらbreak）

について、書いていこうと思います。

それでは！