見出し画像

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杯飲める」程度のサポートをぜひ!