N88-BASICで素数 (2回目)
2021/11/27(土)
N88-BASICで素数 (2回目)
素因数分解
数値や式を因数の積の形にする事を
因数分解といいます
素数のみの因数の積で表す事を
素因数分解と言います
数値n(2以上の整数)を素因数分解するには
i = 2～[√n]で割れば良く
([a]はガウス記号でaを超えない最大の整数
a>0なら切り捨て、a<0なら切り上げ)
n = 18なら
2 ) 18
3 ) 9
3
18 = 2･3･3 = 2･32
となります
アルゴリズム(解法?)
① m = [√n]
② i = 2
③ i > m なら⑥へ
④ q = n / iが
割り切れればiが素因数, n←q, m = [√n]
割り切れなければi←i+1
⑤ ③へ
⑥ nが素因数
単純だが遅い方法がその1です
2で割り切れなくなれば
あとは偶数では割り切れないので
偶数で割ることを省略して処理速度を
上げたのがその2です
今回はこの2種類のアルゴリズムの
処理時間を比較してみました
探せば処理速度の速いアルゴリズムが
いろいろとあると思います
また、C等のコンパイラ言語で書くと
もっと速くなります
今回TIME$を使って時間を表示しています
NL-BASIC,VL-BASIC,XL-BASICの
時刻(DATE$, TIME$)はCLEARやRUNで、
システム時刻に戻ります
Enterのみ入力した場合
127 * 524287 * 6700417
を計算するようにしています
NL-BASICとblg～.zip(prime002.bas)は
このブログ(以下のリンク)から
N88-BASICで素数 (2回目)
素因数分解
数値や式を因数の積の形にする事を
因数分解といいます
素数のみの因数の積で表す事を
素因数分解と言います
数値n(2以上の整数)を素因数分解するには
i = 2～[√n]で割れば良く
([a]はガウス記号でaを超えない最大の整数
a>0なら切り捨て、a<0なら切り上げ)
n = 18なら
2 ) 18
3 ) 9
3
18 = 2･3･3 = 2･32
となります
アルゴリズム(解法?)
① m = [√n]
② i = 2
③ i > m なら⑥へ
④ q = n / iが
割り切れればiが素因数, n←q, m = [√n]
割り切れなければi←i+1
⑤ ③へ
⑥ nが素因数
単純だが遅い方法がその1です
2で割り切れなくなれば
あとは偶数では割り切れないので
偶数で割ることを省略して処理速度を
上げたのがその2です
今回はこの2種類のアルゴリズムの
処理時間を比較してみました
探せば処理速度の速いアルゴリズムが
いろいろとあると思います
また、C等のコンパイラ言語で書くと
もっと速くなります
今回TIME$を使って時間を表示しています
NL-BASIC,VL-BASIC,XL-BASICの
時刻(DATE$, TIME$)はCLEARやRUNで、
システム時刻に戻ります
Enterのみ入力した場合
127 * 524287 * 6700417
を計算するようにしています
NL-BASICとblg～.zip(prime002.bas)は
このブログ(以下のリンク)から
ダウンロードできます
