daily pastebin goal
50%
SHARE
TWEET

Untitled

a guest Jul 11th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math"
  6.     "time"
  7. )
  8.  
  9. const maxNum = 100000 // 素数を調べる最大値
  10.  
  11. func main() {
  12.  
  13.     list := []int{} // 整数リスト
  14.  
  15.     // 整数のリストに初期値2~maxNumをセット(0,1は素数ではないので除外)
  16.     for j := 0; j < maxNum-2; j++ {
  17.         list = append(list, j+2)
  18.     }
  19.  
  20.     // エラトステネスの篩
  21.     start := time.Now()
  22.     furui(list)
  23.     end := time.Now()
  24.  
  25.     // 普通に素数を求める
  26.     start2 := time.Now()
  27.     normal(list)
  28.     end2 := time.Now()
  29.  
  30.     fmt.Printf("エラトステネスの篩 -> %f秒\n", (end.Sub(start)).Seconds())
  31.     fmt.Printf("普通に素数を求める -> %f秒\n", (end2.Sub(start2)).Seconds())
  32. }
  33.  
  34. // エラトステネスの篩
  35. func furui(list []int) {
  36.  
  37.     // ループ最大値取得(maxNumの平方根)
  38.     loopMax := math.Sqrt(maxNum)
  39.  
  40.     var tmp []int
  41.     var target = 1
  42.  
  43.     // 素数を調べる(maxNumの平方根までループすればいい)
  44.     for index := 0; target < int(loopMax); index++ {
  45.         target = list[index] // 素数候補取得
  46.  
  47.         for i := 0; i < len(list); i++ {
  48.             if list[i]%target != 0 {
  49.                 // 素数候補で割り切れる数をふるい落とす(割り切れない数をtmpにセット)
  50.                 tmp = append(tmp, list[i])
  51.             } else if list[i] == target {
  52.                 // 素数候補自身はOK、tmpにセット
  53.                 tmp = append(tmp, list[i])
  54.             }
  55.         }
  56.  
  57.         list = tmp // ふるい落とした結果をセット
  58.         tmp = nil
  59.  
  60.     }
  61.  
  62.     // 素数を表示
  63. //  for _, sosu := range list {
  64. //      fmt.Println(sosu)
  65. //  }
  66. }
  67.  
  68. // 普通に素数を求める
  69. func normal(list []int) {
  70.  
  71.     var tmp2 []int
  72.  
  73.     var isNotSosuFlg = false
  74.  
  75.     // 最大値まで回していき、自分自身以外で割り切れない(約数がない)を求める
  76.     for j := 0; j < len(list); j++ {
  77.  
  78.         // list[0]から始めて自分自身までループし割り切れるか?
  79.         for k := 0; k < len(list); k++ {
  80.             if (list[j]%list[k] == 0) && (list[j] != list[k]) {
  81.                 // 自分自身以外で割り切れたら素数ではない
  82.                 isNotSosuFlg = true
  83.                 break
  84.             } else if list[k] == list[j] {
  85.                 // 上記以外で自分自身は素数
  86.                 break
  87.             }
  88.         }
  89.  
  90.         if !isNotSosuFlg {
  91.             tmp2 = append(tmp2, list[j])
  92.         } else {
  93.             isNotSosuFlg = false
  94.         }
  95.     }
  96.  
  97.     list = tmp2 // 結果をセット
  98.  
  99.     // 素数を表示
  100.     //for _, sosu := range list {
  101. //      fmt.Println(sosu)
  102.     //}
  103. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top