計算量とオーダー記法 ランダウの記法、素数判定、平方根、二分探索、指数関数、対数関数、年齢当てゲーム
問題解決力を鍛える!アルゴリズムとデータ構造 (大槻 兼資(著)、秋葉 拓哉(監修)、講談社)の第2章(計算量とオーダー記法)、章末問題2.3、2.4、2.5の解答を求めてみる。
2.3
2.4
よってk回で当てられる。
2.5
よって、
実際に確認してみる。
コード
package main
import (
"fmt"
"math"
)
func primeON(n int) int {
count := 0
if n <= 1 {
return count
}
for p := 2; p*p <= n; p++ {
count++
if n%p == 0 {
return count
}
}
return count
}
func main() {
for n := 2; n <= 50; n++ {
fmt.Println(n, primeON(n), math.Sqrt(float64(n)))
}
}
入出力結果
% go run ./main.go
2 0 1.4142135623730951
3 0 1.7320508075688772
4 1 2
5 1 2.23606797749979
6 1 2.449489742783178
7 1 2.6457513110645907
8 1 2.8284271247461903
9 2 3
10 1 3.1622776601683795
11 2 3.3166247903554
12 1 3.4641016151377544
13 2 3.605551275463989
14 1 3.7416573867739413
15 2 3.872983346207417
16 1 4
17 3 4.123105625617661
18 1 4.242640687119285
19 3 4.358898943540674
20 1 4.47213595499958
21 2 4.58257569495584
22 1 4.69041575982343
23 3 4.795831523312719
24 1 4.898979485566356
25 4 5
26 1 5.0990195135927845
27 2 5.196152422706632
28 1 5.291502622129181
29 4 5.385164807134504
30 1 5.477225575051661
31 4 5.5677643628300215
32 1 5.656854249492381
33 2 5.744562646538029
34 1 5.830951894845301
35 4 5.916079783099616
36 1 6
37 5 6.082762530298219
38 1 6.164414002968976
39 2 6.244997998398398
40 1 6.324555320336759
41 5 6.4031242374328485
42 1 6.48074069840786
43 5 6.557438524302
44 1 6.6332495807108
45 2 6.708203932499369
46 1 6.782329983125268
47 5 6.855654600401044
48 1 6.928203230275509
49 6 7
50 1 7.0710678118654755
%