算数04 最小公倍数 最大公約数 素数 垂水共之 約数diviser・因数factor • ある整数ｎを割り切れる整数をｎの約数という • 例 n=12の場合 – 12÷1=12 – 12÷2=6 – 12÷3=4 – 12÷4=3 – 12÷6=2 – 12÷12=1 12の約数は 1，2，3，4，6，12の6個 素数と合成数 • 素数の定義 – １とその数自身でしか割り切れない ２以上の自然数 １は素数でない – 個数 ・ 合成数とは － 素数でない数 • 無数にある – 見つかっている最大の素数 • 257885161‐1=581887266・・・724285951 1742万5170桁 素数 • 50までの素数 – 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 • 素数の見つけ方 – エラトステネスの篩（ふるい） • メルセンヌ素数（Mersenne prime） – メルセンヌ数 – 素数のメルセンヌ数 – 2p‐1が素数pも素数 2p‐1 21-1= 1 22-1= 3 23-1= 7 24-1= 15 25-1= 31 26-1= 63 27-1=127 １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ １６ １７ １８ １９ ２０ ２１ ２２ ２３ ２４ ２５ ２６ ２７ ２８ ２９ ３０ ３１ ３２ ３３ ３４ ３５ ３６ ３７ ３８ ３９ ４０ ４１ ４２ ４３ ４４ ４５ ４６ ４７ ４８ ４９ ５０ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ １６ １７ １８ １９ ２０ ２１ ２２ ２３ ２４ ２５ ２６ ２７ ２８ ２９ ３０ ３１ ３２ ３３ ３４ ３５ ３６ ３７ ３８ ３９ ４０ ４１ ４２ ４３ ４４ ４５ ４６ ４７ ４８ ４９ ５０ １００までの素数を求めよう １ １１ ２１ ３１ ４１ ５１ ６１ ７１ ８１ ９１ ２ １２ ２２ ３２ ４２ ５２ ６２ ７２ ８２ ９２ ３ １３ ２３ ３３ ４３ ５３ ６３ ７３ ８３ ９３ ４ １４ ２４ ３４ ４４ ５４ ６４ ７４ ８４ ９４ ５ １５ ２５ ３５ ４５ ５５ ６５ ７５ ８５ ９５ ６ １６ ２６ ３６ ４６ ５６ ６６ ７６ ８６ ９６ ７ １７ ２７ ３７ ４７ ５７ ６７ ７７ ８７ ９７ ８ １８ ２８ ３８ ４８ ５８ ６８ ７８ ８８ ９８ ９ １０ １９ ２０ ２９ ３０ ３９ ４０ ４９ ５０ ５９ ６０ ６９ ７０ ７９ ８０ ８９ ９０ ９９ １００ 素因数分解 • 合成数を素数の積で表そう 12 2 2 3 2 3 2 • １２の約数は何個 – (2+1)×(1+1)=3×2=6 1 12 2 2 3 2 2 31 (20 30 ) (2 2 31 ) 112 (21 30 ) (21 31 ) 2 6 (2 2 30 ) (20 31 ) 4 3 (20 31 ) (2 2 30 ) 3 4 (21 31 ) (21 30 ) 6 2 (2 2 31 ) (2 2 30 ) 12 1 ６０の約数は何個、全て求めよう 60 2 2 3 5 2 3 5 2 公約数・最大公約数 • 2つ（以上）の自然数の同じ約数 • 例 – 12の約数 １、２、３、４、６、１２ – 16の約数 １、２、４、８、１６ – 12と16の公約数 １、２、４ • 最大公約数 GCD Greatest Common Divisor – 最も大きい公約数 倍数・公倍数・最少公倍数 • ある数を整数倍した数を元の数の倍数という – 例 ３の倍数 ‐9,‐6,‐3,0,3,6,9 • 2つ（以上）の数の倍数で同じものを公倍数と いう – 例 ３と５の公倍数 • ３の倍数 • 5の倍数 ‐15,‐12,‐9,‐6,‐3,0,3,6,9,12,15 ‐15,‐10,‐5,0,5,10,15 • ０は倍数から除くことが多い • ０でない最小の正の公倍数を最小公倍数と いう LCM Least Common Multiple ユークリッドの互除法 最大公約数の求め方 • aとｂの最大公約数dを求めたい • a=bq+r a÷b=q…r a>b>r • 「aとbの最大公約数」は 「bとrの最大公約数」と同じ！ aとbがdで割り切れる のであれば rもdで割り切れる • 460と322の最大公約数を求めたい • 460÷322=1…138 • 「460と322の最大公約数」は 「322と138の最大公約数」と同じ！ • 460と322の最大公約数を求めたい • 460÷322=1…138 • 「460と322の最大公約数」は 「322と138の最大公約数」と同じ！ • 460÷322=1…138 • 138÷46=3…0 • 322÷138=2…46 • 138=46×3 • 138÷46=3…0 • 46=46×1 138と46との最大公約数は46 やってみよう • ４５と３４５の最大公約数 • １２５と１５の最大公約数 • ２５２と105の最大公約数 • ６３０と３００の最大公約数 • 1071と1029の最大公約数 最小公倍数の求め方 ２）８ ２０ ３０ ４ １０ １５ ２）４ １０ １５ ２ ５ １５ ５）２ ５ １５ ２ １ ３ ２）８ ２０ ３０ ２）４ １０ １５ ５）２ ５ １５ ２ １ ３ LCM=2×2×5×2×1×3 =120 やってみよう • ６と９と１５の最小公倍数 • ６０と１５４と５０４の最小公倍数
© Copyright 2024 ExpyDoc
