R:素数を。求める。Part2
こんにちは。今回の記事は下の記事の続きです。
やること
・割り切れる数はn/2以下でしか存在しない
・3回以上割り切れたら中断(K≧3になったらbreak)
今のとこのコード
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)
割り切れる数はn/2以下でしか存在しない
10を割り切れる可能性のある数として、6以上はないように
nを割り切れる可能性のある数として、n/2以上は存在しないので
for (j in 1:i)
→
for (j in 2:floor(i/2))
このようにコードを変更することで、可能になります。
時間測るのは最後にやります。
次は
3回以上割り切れたら中断(K≧3になったらbreak)
3回以上割り切れたら、その時点でその数の検証を終了することで、時間の短縮が出来ます。
for (j in 1:i) {
if( i %% j == 0)
k <- k+1
}
のところを
for (j in 1:i) {
if( i %% j == 0)
k <- k+1
if( k >= 3)
break
}
に変えることで、
3回割り切れた時に次のループに進むようになります。
この2つを組み合わせたものがこちら
cN <- 10000
So <- NULL
Timer <- proc.time()
for (i in 2:cN) {
k <- 0
for (j in 2:floor(i/2)) {
if( i %% j == 0)
k <- k+1
if( k >= 1)
break
}
if(k == 0)
So <- i
}
print(( proc.time() -Timer)[3])
print(So)
ここまでの3パターンの時間を計ってみると
タイム計測
用いるコードはこちら
##条件設定
cN <- 10000
So <- NULL
##Ver1 素数を求める
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
}
Ver1 <- (( proc.time() -Timer)[3])
print(So)
##Ver2 n/2以下のときのみ考える
Timer <- proc.time()
for (i in 2:cN) {
k <- 0
for (j in 2:floor(i/2)) {
if( i %% j == 0)
k <- k+1
}
if(k == 0)
So <- i
}
ver2 <- (( proc.time() -Timer)[3])
print(So)
##Ver3 K=3のときbreak
Timer <- proc.time()
for (i in 1:cN) {
k<-0
for (j in 1:i) {
if( i %% j == 0)
k <- k+1
if( k >= 3)
break
}
if(k == 2)
So <- i
}
Ver3 <- (( proc.time() -Timer)[3])
print(So)
##Ver4 2と3の組み合わせ
Timer <- proc.time()
for (i in 2:cN) {
k <- 0
for (j in 2:floor(i/2)) {
if( i %% j == 0)
k <- k+1
if( k >= 1)
break
}
if(k == 0)
So <- i
}
Ver4 <- (( proc.time() -Timer)[3])
print(So)
## 時間測定
Ver1
Ver2
Ver3
Ver4
Ver2/Ver1
Ver3/Ver1
Ver4/Ver1
そして、結果がこちら
> Ver1
elapsed
8.36
> Ver2
elapsed
4.18
> Ver3
elapsed
1.76
> Ver4
elapsed
0.62
> Ver1/Ver2
elapsed
2
> Ver1/Ver3
elapsed
4.75
> Ver1/Ver4
elapsed
13.48387
・割り切れる数はn/2以下でしか存在しない①
・3回以上割り切れたら中断(K≧3になったらbreak)②
・①と②の組み合わせ③
①2倍
②4.75倍
③13.5倍
まとめ
素数を早く求めるという点ではこのくらいでいいのかなと思ってます。
最速を目指すならエラトステネスの篩の実装が求められるので、挑戦してみようと思います。
最後まで読んでくれてありがとう!読み終わって内容が面白ければ、「お疲れ様」の意味を込めて「缶コーヒー1杯飲める」程度のサポートをぜひ!