数学の
まど
素因数分解を利用した約数の求め方
ある数を素因数分解して,その数の約数を求める方法を考えてみましょう。
42 の約数を求めてみましょう。
まず、1と42は42の約数です。
次に,42 を素因数分解すると
かけ算の式で
表すと、約数が
見つけられるね。
42 = 2×3×7
となります。2,3, 7のかけ算の組み合わせを考えると
42 = 2×(3×7) =2× 21
42 = 3×(2×7) =3×14
42 = 7×(2×3) =7×6
したがって,42 の約数は
1,2, 3, 6, 7, 14, 21, 42
○70の約数を求めてみましょう。
また,63 の約数を求めてみましょう。
数学の
まど
エラトステネスのふるい
素数を見つけるのに
エラトステネスのふるいとよばれる。
素数でない数をふるい落としていく
方法があります。
この方法で,100 までの素数を
求めてみましょう。
3
4 56
7
8
9
10 11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
1 1は素数でないから消す。
2 2に○印をつけて残し、
それより大きい2の倍数を消す。
3 残った数のうち, 最小の数3に
○E印をつけて残し,それより
大きい3の倍数を消す。
4 残った数のうち, 最小の数に
○印をつけ,それより大きい
その数の倍数を消す作業を続ける。
5 OE印のついた数が素数である。
43
44
45 46
47
48
49
50 51
52 53 54
55 56 57
58 59 60
61
62 63 64
65
66
67 68 69
70
71
72
73
74 75
76
77
79
80
81
82 83 84
85
86
87
88 89 90
91
92
93
94 95
96
97
98
99 100
C
