fx-5800P 素因数分解 - 高速化

追記修正 2019/08/28

今回は、fx-5800P の素因数分解プログラムの高速化の話題です。

素因数分解の一般的な方法は、"エラストテレスのふるい" と言われるものです。最初に入力した数 N を小さい順に素数で割り算を繰り返す方法です。最大の素因数は N の平方根以下の整数なので、平方根以下の整数を対象に2と3以上の奇数で割り算を行う方法で fx-5800P での素因数分解プログラムを作っています。
⇒ fx-5800P 素因数分解 - バグ修正と表示変更

さらに高速化する方法は無いものかと、色々と考えたり、試したりしていました。
例えば Casio 関数電卓の素因数分解 など。



最速の素因数分解プログラム

最近、目からうろこの高速化を達成した記事を見つけました。
A fast prime factorizing program for Casio fx-5800P 
このトピックで、作者の slugrustle 様 は、2つのプログラムを公開されています。いずれもプログラム名は FACTOR です。
オリジナルは、上のサイトをご覧ください。

これらには、面白い工夫がなされています。その部分には手を付けず、表示やユーザーインターフェースの不具合(と私が思うだけですが...)を解消するために、チョット変更しました。


1本目のプログラムの変更版:
結果の表示を 3^2 と乗数を表示し、List にも乗数の結果が FREQ に反映するように変更しました。
FACTOR-M1 のダウンロード

FACTOR-M1_1 FACTOR-M1_2 
FACTOR-M1 の結果出力 - 左: 乗数表示、- 右: [MODE] [3] で現れる List表示


2本目のプログラムの変更版:
オリジナルプログラムでは、結果表示画面を、複数ページで切り替えて自由に見られるようになっています。[EXE] [▲] [▶] [+] で次のページを表示、[(ー)] [▼] [◀] で前のページを表示、[EXIT] [DEL] でプログラムを終了するようになっています。計算が高速化しているだけでなく、結果表示も良くなっています。

このキーの使い方がチョット馴染まないので、[▼] で次のページ、[▲] で前のページ、[+] は使えないようにし、指定以外のキーを押した時の誤動作を抑制するように修正しました。時間をかけて計算できた結果が、誤動作で見えなくなるのは嫌ですから...
さらに、オリジナルはキーを軽く押しても応答せず長押しが必要、つまり応答がとても悪いので、キー入力待ちを最小のループにして応答を十分高速にしました。軽くキーを1回押すだけで、チョット待ちますが必ず画面が変わります。
またオリジナルでは結果表示一覧で素因数として 1 が表示されますが、1 は素数ではないので、素因数として 1 が表示されないように修正しました。
FACTOR-F1 のダウンロード

FACTOR-F1_1  FACTOR-F1_2 
FACTOR-F1 の結果表示 - 全結果を画面切り替えで確認、左: 2/1ページ、右: 2/2ページ


比較のための以前作った PRIME DECOMP:
PRIME DECOMP のダウンロード

Prime_Decomp_2 Prime_Decomp_3 


上記でダウンロードしたZIPファイルには、それぞれ CCL ファイルと TEXT ファイルが含まれています。CCL ファイルは CcLinker を使って fx-5800P に転送できます。或いは、下のリンクからテキストファイルを参考にしてください。



計算時間の比較

先ずは、fx-5800P でどのくらい高速化されたかの結果を示します。

PRIME DECOMP
ソースコード
FACTOR-M1
ソースコード
FACTOR-F1
ソース (メインルーチン)
ソース (サブルーチン)
123,456,789
= 32 x 3607 x 3803
170 秒60 秒
3 倍高速化
42 秒
4 倍高速化
6,666,666,667
= 19 x 1627 x 215659
77 秒27 秒
3 倍高速化
20 秒
4 倍高速化
7,849,516,203
= 32 x 9811 x 88897
458 秒165 秒
3 倍高速化
111 秒
4 倍高速化

1本目の FACTOR-M1 で3倍高速化、さらに2本目の FACTOR-F1 は4倍高速化されていることが分かります。

素因数分解は、与えられた数を小さい数から順に割ってゆく時、その操作の回数を減らせば、高速化に繋がります。
PRIME DECOMP では入力した数に、先ず平方根をとって一気に探査範囲を狭め、2と3以上の奇数で小さい方から順に割り算してゆく作戦です。

一方で、理想的なのは、小さい素数から素数だけで順に割り算してゆくことです。それには素数リストが必要ですが、それがあれば苦労しません。素数を算出する計算式などありません。

さて、slugursite様の工夫は、高い確率で素数を見つけるだけでなく、割り算する候補 (例えば、2 や 3 だけでなく、一旦割り算で使った素数の倍数) を効果的にふるい分ける手法にあります。そして、最初の FACTOR-M1 よりも 次の FACTOR-F1 の方が、素数を見つける確率が高くなっているので、さらに高速化されています。



最速プログラムでの工夫 [2019/07/31]

読者のまつ様から、高速プログラムの考え方をご説明頂きました。私はこれに大変納得しましたので、それを掲載致します。以前の記述は撤回させて頂きます。

素因数分解プログラムで通常行われている割り算では,「2,および,3以上の奇数」を割る数としています。
これですと,ご存知のように,例えば3で割り切った後に9でも割るという無駄が出てしまいます。
FACTOR-M1は,「2, 3, 3より大きい3の倍数を除く奇数」を割る数としており,3で割ったあと9や15で割ることはないようにしています。

3より大きい3の倍数を除く奇数について考えてみます。

まず,3より大きい3の倍数でない整数は次の(1),(2)のどちらかです。
 3m+1 (1)
 3m+2 (2)
 (m>=1)

次に(1),(2)が奇数となる式をそれぞれ求めます。

(1)は (2m+1)+m と変形できます。2m+1 は奇数ですから,(1)が奇数であるためには m が偶数である必要があります。そこで m=2n (n>=1) とおけば,(1)は 6n+1 となります。

(2)は 2(m+1)+m と変形できます。2(m+1) は偶数ですから,(2)が奇数であるためには m が奇数である必要があります。そこで m=2n+1 (n>=1) とおけば,(2)は 6n+5 となります。

5とこれらの式を並べ,さらに,隣り合う式の差も書き加えると次のようになります。(n=1とします)
式の並び隣り合う式の差
52
6n + 14
6n + 52
6(n+1) + 14
6(n+1) + 52
6(n+2) + 14
6(n+2) + 52
:
:
:
:
このような訳で,2, 4, 2, 4, ... と加算していると思われます。
この繰り返しは,6n+1 および 6n+5 の式からも分かるように,2と3の最小公倍数6を周期としています。

FACTOR-F1は,これを拡張して,割る数として
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
を順番に求めていく方法をとっていると思われます。
2,3,5,7の最小公倍数は210ですから,隣り合う割る数の差(2,4,6,8など)の並びは210が1周期です。
FACTOR-F1の場合は,13+210n〜13+210(n+1)-1 [n>=0]の範囲で,2,3,5,7のいずれの倍数でもない整数を並べて,隣り合う整数の差をリストにしていると思われます。

ちなみに,13〜222の210個の整数のうち,
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
の個数は,FACTOR-F1の「While 1」の下にある
 B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1
のパターンの行数と同じ48個です。

48個となる理由は次の通りです。

まず,2,3,5,7の倍数に関わるそれぞれの個数を求めます。

2の倍数の個数=210/2=105
3の倍数の個数=210/3= 70
5の倍数の個数=210/5= 42
7の倍数の個数=210/7= 30
 
2と3の公倍数の個数= 6の倍数の個数=210/ 6=35
2と5の公倍数の個数=10の倍数の個数=210/10=21
2と7の公倍数の個数=14の倍数の個数=210/14=15
3と5の公倍数の個数=15の倍数の個数=210/15=14
3と7の公倍数の個数=21の倍数の個数=210/21=10
5と7の公倍数の個数=35の倍数の個数=210/35= 6
 
2,3,5の公倍数の個数= 30の倍数の個数=210/ 30=7
2,3,7の公倍数の個数= 42の倍数の個数=210/ 42=5
2,5,7の公倍数の個数= 70の倍数の個数=210/ 70=3
3,5,7の公倍数の個数=105の倍数の個数=210/105=2
 
2,3,5,7の公倍数210の個数=210/210=1

重複を考慮すると,
2,3,5,7のいずれかの倍数の個数
=(105+70+42+30)-(35+21+15+14+10+6)+(7+5+3+2)-1
=162

従って,2,3,5,7のうちどの倍数でもない整数の個数は,
 210-162=48
で 48個となります。


素因数分解の正しい動作を検証

この作者は自分のプログラムを検証するテストプログラムまで作って、ソースコード (C++) を公開しています。fx-5800P 用なので、素因数分解する数は最大10桁と決まっています。この条件下でアルゴリズムの正しさを検証しています。

検証プログラムのソースコードが公開されています。そこで Visual Studio 2019 Community でビルドしました。


 FACTOR-F1 のテストプログラム Factor.exe のダウンロード [2019/08/28 リンクを修正]

コマンドプロンプトで、Factor.exe のあるデイレクトリに移動し、そこで

 Factor 1000 50000 4

と入力してエンターキーで実行すると、1000 から 50000まで 4 刻みで入力を変化させて FACTOR-F1 を実行した結果を一気に連続して自動実行してくれます。そして、結果が素数がどうか判定し、素数でないものが出てくるとエラーを出し、素数であれば実行を継続します。正常終了すれば、正しく素因数分解が実行されたことになります。

factor_1
正常終了しているので、1000 から 50000 までの素因数分解は問題ないことが検証されました。


fx-5800P 用のプログラムなので、入力値は 1 ~ 9,999,999,999 (10桁) の範囲なので、完璧にテストするには、

 Factor 1 9999999999 1

とすれば良いのですが、試しに私のPCだと、1晩で150億回分の検査が済みました。 10桁に相当する (1000億 - 1) 個全部のテストは、夜のみ終夜運転で計算させるとして1週間程度必要になりそうです。

factor_2
1 ~ 9,999,999,999 までのテスト中

テストが正常終了すれば、このアルゴリズムが正しいことが検証されます。但し、他のパラメータ設定でも正しい組み合わせは有りそうです。



グラフ関数電卓用に移植

FACTOR-F1 をグラフ関数電卓用に移植しました。素因数分解の計算部分は変更の余地がありませんが、結果表示は7行全部を使うように変更しました。

グラフ関数電卓用 FactorG のダウンロード

FactorG 
FactorG の結果表示


今回は、slugrustle 様による投稿の解説記事になってしまいましたが、私としては十分楽しませてもらったので、記事にして残そうと思いました。




応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


keywords: プログラム関数電卓、fx-5800P、素因数分解、プログラミング、Casio Basic

リンク集 | ブログ内マップ

関連記事

テーマ : プログラム関数電卓
ジャンル : コンピュータ

コメントの投稿

非公開コメント

Re: 素因数分解プログラム・自己流

サットルー様

初めてのコメント、ありがとうございます。


> 私も数ヶ月前までfx-5800pでの素因数分解プログラム作成に熱中していました。その時作ったプログラムもFACTOR-F1と同じくらいの速度でした。(123456789の素因数分解で42秒ほど)
> 手法は2,3でまず割って、それから5から始まり、2,4,2,4…と割る数を増やしていくものです。

まさに同じようなアルゴリズムをお考えになって実装されていたのですね。
いや、素晴らしいです!

素因数分解の高速化については、このアルゴリズムを理解するためのご説明をまつ様からコメントで頂き、それを読んで初めて分かった気になっているところです。


> 実装方法が違うと速度が大きく異なるということです。具体的には、whileループよりforループの方が速い、などです。

fx-5800P のようなプアなCPUでは、高速化を目的として処理を追加すると、そのために制御構造が複雑になり、却って全体の処理速度が遅くなるといった事例を、とても多く経験しています。

そこで、代表的なコマンド類で特に処理の遅いものの実行速度を実測したくらいです。今ではその結果を参考にしてプログラムを書いています。

fx-5800P:変数アクセス、比較・論理演算、条件分岐の速度比較:
https://egadget.blog.fc2.com/blog-entry-152.html

この結果を元にして、実際に公開していたプログラムを2倍ほど高速化した事例を記事で紹介したりしています。遅い処理を無くすことを主眼にしてアルゴリズム全体を見直した結果です。
https://egadget.blog.fc2.com/blog-entry-154.html

いい変えれば最初のコードが良くなかっただけですが、却ってfx-5800Pプログラムの高速化の一般的な技法が整理できたと思っています。


For文が DoやWhileよりも速いというのは、ディクリメント/インクリメントやループ継続判定の余計な記述が不要な分だけそうなのかと思っていましたが、まだ実際に実験していませんでした。今度機会があれば、やってみようと思います。


またコメントを頂けると嬉しいです。

素因数分解プログラム・自己流

初めてコメント致します。
私も数ヶ月前までfx-5800pでの素因数分解プログラム作成に熱中していました。その時作ったプログラムもFACTOR-F1と同じくらいの速度でした。(123456789の素因数分解で42秒ほど)
手法は2,3でまず割って、それから5から始まり、2,4,2,4…と割る数を増やしていくものです。
これを作っている時に気づいたことは、アルゴリズムが同じでも、実装方法が違うと速度が大きく異なるということです。具体的には、whileループよりforループの方が速い、などです。
また、割る数が割られる数の平方根に達するまで繰り返すですが、達したかどうかの判定はそこまで頻繁に行う必要はないかもしれない、とも考えました。つまり、割る数を増やすたびに判定を行うのではなく、例えば10回に1回程度の頻度で十分なのではないか、ということです。この方法で大きい数の素因数分解の速度向上が望めますが、小さい数の速度が犠牲になるように思えます。しかし、小さい数はもともと高速に処理できるのであまり気にならない、というのが私の結論です。
プログラム初心者なので、的外れなことを言っていたらすみません。

Re: Re: FACTOR-M1,F1の動作について

やすさん

まつです。

記事に引用頂きありがとうございます! あの部分をこう書けばよかったかなという点が色々あり,そのままはちょっと恥ずかしい気もします。
「この方が分かりやすい」と思われましたら,どんどん変更して頂いて構いません!

やすさんの記事でFACTOR-M1,F1を知った時は正直びっくりしました。
自分もそれまで割り算するループの部分などをそれなりに工夫してきて,これ以上の大幅な高速化は無理と思っていたところに,それをはるかに超えるパフォーマンスとは・・・

FACTOR-F1の方はソースコードに何やら似たような行がずらずらと並んで怪しさ満点ですが,FACTOR-M1は単純に+2,+4,...するだけ。それなのに,5,7,11,13,17,19,23,25,29, とほぼ素数が並ぶ。これには感動しました。
でも,素数以外が若干混じるのはいいとして,逆に素数が抜けちゃうことはないんだろうか・・・とも。

そう思っていたある時,以前の素因数分解の記事に寄せられていたすけっぴいさんのコメントで
「3以外の3の倍数は素数ではないという前提から、素因数候補の数が減る。同様に5、7、11...の倍数も」
とあったのを思い出し,これが大きなヒントとなりました。

「FACTOR-M1の+2,+4,...で得られる数は確かにうまく3の倍数を避けているなあ。でも何でこれで避けられるんだろう?」と考えたら最後,三日三晩寝ずにうーんうーんとうなりながら・・・というのはさすがに大げさですが,先日投稿したような内容をひねりだしました。

でも,これ以上の,つまり2,3,5,7,11のいずれの倍数でもない整数のみで割り算していくプログラムの作成はやめた方が良さそうです。ソースコードに怪しい行が(おそらく)480個,ずらずらと並ぶことになるかと・・・

ではまた!

Re: FACTOR-M1,F1の動作について

まつ様

管理人のやすです。


まつ様、凄すぎます。

とても説得力のあるご説明、ありがとうございます。

頂いた解説を、そのまま本文に使わせて頂いたのですが、よろしいでしょうか?
ご都合が悪いようでしたら、おっしゃってください。適切に対処致します。


FACTOR-M1,F1の動作について

やすさん

FACTOR-M1,F1の動作について考えてみました。
以下,長文で失礼します。

素因数分解プログラムで通常行われている割り算では,「2,および,3以上の奇数」を割る数としています。
これですと,ご存知のように,例えば3で割り切った後に9でも割るという無駄が出てしまいます。
FACTOR-M1は,「2, 3, 3より大きい3の倍数を除く奇数」を割る数としており,3で割ったあと9や15で割ることはないようにしています。

3より大きい3の倍数を除く奇数について考えてみます。

まず,3より大きい3の倍数でない整数は次の(1),(2)のどちらかです。
 3m+1 (1)
 3m+2 (2)
 (m>=1)

次に(1),(2)が奇数となる式をそれぞれ求めます。

(1)は (2m+1)+m と変形できます。2m+1 は奇数ですから,(1)が奇数であるためには m が偶数である必要があります。そこで m=2n (n>=1) とおけば,(1)は 6n+1 となります。

(2)は 2(m+1)+m と変形できます。2(m+1) は偶数ですから,(2)が奇数であるためには m が奇数である必要があります。そこで m=2n+1 (n>=1) とおけば,(2)は 6n+5 となります。

5とこれらの式を並べ,さらに,隣り合う式の差も書き加えると次のようになります。(n=1とします)
式の並び  隣り合う式の差
5
2
6n+1
4
6n+5
2
6(n+1)+1
4
6(n+1)+5
2
6(n+2)+1
4
6(n+2)+5
2
... ...

このような訳で,2, 4, 2, 4, ... と加算していると思われます。
この繰り返しは,6n+1 および 6n+5 の式からも分かるように,2と3の最小公倍数6を周期としています。

FACTOR-F1は,これを拡張して,割る数として
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
を順番に求めていく方法をとっていると思われます。
2,3,5,7の最小公倍数は210ですから,隣り合う割る数の差(2,4,6,8など)の並びは210が1周期です。
FACTOR-F1の場合は,13+210n〜13+210(n+1)-1 [n>=0]の範囲で,2,3,5,7のいずれの倍数でもない整数を並べて,隣り合う整数の差をリストにしていると思われます。

ちなみに,13〜222の210個の整数のうち,
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
の個数は,FACTOR-F1の「While 1」の下にある
 B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1
のパターンの行数と同じ48個です。

48個となる理由は次の通りです。

まず,2,3,5,7の倍数に関わるそれぞれの個数を求めます。

2の倍数の個数=210/2=105
3の倍数の個数=210/3= 70
5の倍数の個数=210/5= 42
7の倍数の個数=210/7= 30
 
2と3の公倍数の個数= 6の倍数の個数=210/ 6=35
2と5の公倍数の個数=10の倍数の個数=210/10=21
2と7の公倍数の個数=14の倍数の個数=210/14=15
3と5の公倍数の個数=15の倍数の個数=210/15=14
3と7の公倍数の個数=21の倍数の個数=210/21=10
5と7の公倍数の個数=35の倍数の個数=210/35= 6
 
2,3,5の公倍数の個数= 30の倍数の個数=210/ 30=7
2,3,7の公倍数の個数= 42の倍数の個数=210/ 42=5
2,5,7の公倍数の個数= 70の倍数の個数=210/ 70=3
3,5,7の公倍数の個数=105の倍数の個数=210/105=2
 
2,3,5,7の公倍数210の個数=210/210=1

重複を考慮すると,
2,3,5,7のいずれかの倍数の個数
=(105+70+42+30)-(35+21+15+14+10+6)+(7+5+3+2)-1
=162

従って,2,3,5,7のうちどの倍数でもない整数の個数は,
 210-162=48
で 48個となります。

Re:Re: Re: Re: Re:Re: 素因数分解の結果表示

管理人様、こんにちは!

>わっ、そうですか?
>普通だと思っていたことが、そうでないと指摘されることが結構あるので、またやっちゃった感満載です(^_^;

より画面の広いグラフ電卓だと縦表示でも一度に表示可能になるので、縦表示が最適表示になってきますね。(^^)



まつ様、こんにちは!

>(CcLinkerには興味がありますが,今のところ手が出ず・・・)

fx-5800PとPCを連携させるには最適最強のツールなのでぜひぜひ。(^^)


>今回,電卓の素因数分解と同じような表示をfx-5800Pでできないだろうか,というところが出発点です。

他のプログラム電卓ではそうしたくでも出来ないものが多いのでfx-5800Pの強力なアドバンテージですね。(^^)

Re: Re: Re: Re:Re: 素因数分解の結果表示

まつ様

管理人のやすです。


> やすさん,記事として取り上げていただき光栄です。どうもありがとうございます。
> あと,ソースコードにタイプミスがあり申し訳ありません。

こちらこそ、面白い題材を頂き、有り難いです。

タイプミスは、私が記事でしょっちゅうやっているので、お気になさらないでください。
おっしゃるような開発スタイルでは、転記ミスは仕方ないと思います。

今後も、プログラムを投稿頂ければうれしいです。

Re: Re: Re:Re: 素因数分解の結果表示

やすさん,sentaroさん

やすさん,記事として取り上げていただき光栄です。どうもありがとうございます。
あと,ソースコードにタイプミスがあり申し訳ありません。
プログラムを作成は,「PCで作成し,それを見ながらfx-5800pに手入力」「fx-5800pで修正したらPCの方にもそれを手作業で反映」
というあまり効率的でないことをしてます。その時にミスしてしまいました。
(CcLinkerには興味がありますが,今のところ手が出ず・・・)

sentaroさん,はじめまして。コメントありがとうございます。
今回,電卓の素因数分解と同じような表示をfx-5800Pでできないだろうか,というところが出発点です。

> >素数を縦に並べるのが、ぱっと見て最も分かりやすう方法だと思い込んでいました。
>
> 電卓の素因数分解では一行で結果が表示されるので、縦に並べる管理人様方式が斬新なのかもしれません。(^^;

私もその通りだと思います。詰め込んだ表示より整理されていて見やすいです!
この方法も好きです。

Re: Re:Re: 素因数分解の結果表示

sentaro様、まつ様

管理人のやすです。

記事で、ソースコードが最後まで表示されない問題があったので、対処しました。
直に書くと、何かの記号が html に悪さをして、それ以降の記述が消えてしまう症状のようですから、ソースコードを画像化して貼り付けました。


https://egadget.blog.fc2.com/blog-entry-701.html



sentaro様、
> >素数を縦に並べるのが、ぱっと見て最も分かりやすう方法だと思い込んでいました。
>
> 電卓の素因数分解では一行で結果が表示されるので、縦に並べる管理人様方式が斬新なのかもしれません。(^^;

わっ、そうですか?
普通だと思っていたことが、そうでないと指摘されることが結構あるので、またやっちゃった感満載です(^_^;



Re:Re: 素因数分解の結果表示

まつ様、はじめまして!

結果が一画面で見れるのはとても良いと思います。
4行表示ならではのプログラムですね。
ありがとうございます!(^^)


管理人様、
Cclinkerでいただきました。(^^)

>素数を縦に並べるのが、ぱっと見て最も分かりやすう方法だと思い込んでいました。

電卓の素因数分解では一行で結果が表示されるので、縦に並べる管理人様方式が斬新なのかもしれません。(^^;

Re: 素因数分解の結果表示

まつ様

管理人のやすです。

ご投稿、ありがとうございます。

面白いご提案ですね。
正直に言いますと、これまで考えたこともありません。

素数を縦に並べるのが、ぱっと見て最も分かりやすい方法だと思い込んでいました。

私にとって意外な発見なので、1つの記事で紹介致しました。

よろしければご覧下さい。
https://egadget.blog.fc2.com/blog-entry-701.html


素因数分解の結果表示

はじめまして。
いつも楽しく拝見しています。
特に素因数分解プログラムのシリーズ記事は大変興味深いです。

私は素因数分解の方法そのものではなく結果表示について考えてみました。
やすさんは1行に"×",素数,べき乗数を1組ずつ表示されていますが,
できるだけ詰めて表示したかったわけです。
例えば 360 については,
2^3×3^2×5<END>
という具合です。

ある限定された範囲の整数を素因数分解した時,より多くの素因数(桁は小さい)に
分解されて"×"や"^"が多く使われるほうが,より長い表示となる傾向があります。
以下は6692786100の素因数分解結果ですが,9999999999を超えない整数では,
これが一番長いのではないかと思います。

2^2×3^2×5^2×7×11×13×17×19×23<END>   (33文字) 

これを各行にきっちり16文字ずつ詰めると,以下のように3行で収まります。

2^2×3^2×5^2×7×11
×13×17×19×23<END
>

つまり,9999999999を超えない整数の素因数分解結果は16桁×4行に収まるので,
スクロールや画面更新等は無しで済むと考えています。

以下は私が作成したソースコードです。
Lbl9以降が表示部分です。
やすさんのPRIME DECOMPと同様,素因数分解の結果をZ[]配列に入れています。

なお,16桁×4行に表示するにあたり,
「"<END>"および一つの素因数は2行に分れた表示をしない(=途中で改行しない)」
という仕様にしました。(というか,分けるほうが大変)
先ほどの例では以下のようになります。

2^2×3^2×5^2×7×11
×13×17×19×23
<END>

=====ここからソースコード=====
?→N
N→M
Cls
If N<1:Then "MUST BE NUM>0":Stop:IfEnd
If N=1:Then Locate 1,1,"1<END>":Stop:IfEnd

20→DimZ
0→B

Int(M÷2)→H
While H+H=M
H→M:Isz B:Int(M÷2)→H
WhileEnd
If B>0:Then
2→Z[1]:B→Z[2]:0→B:3→D
Else
1→D
IfEnd
If M=1:Then Goto 9:IfEnd

3→S
√(M)→K
while S≦K

Int(M÷S)→H
While H×S=M
H→M:Isz B:√(M)→K:Int(M÷S)→H
WhileEnd
If B>0:Then S→Z[D]:Isz D:B→Z[D]:0→B:Isz D:IfEnd
Isz S:Isz S
WhileEnd

If M≠1:Then M→Z[D]:Isz D:1→Z[D]:Isz D:IfEnd

lbl 9
1→C:1→U:1→V:0→W

while C<D

If W=1:Then
If U>16:Then Isz V:1→U:IfEnd
Locate U,V,"×":Isz U
Else
1→W
IfEnd

Int(log(Z[C]))→K:Isz K
If U+K>17:Then Isz V:1→U:IfEnd
Locate U,V,Z[C]:U+K→U
Isz C
If Z[C]>1:Then
If U>16:Then Isz V:1→U:IfEnd
Locate U,V,"^[":Isz U
Int(log(Z[C]))→K:Isz K
If U+K>17:Then Isz V:1→U:IfEnd
Locate U,V,Z[C]:U+K→U
IfEnd
Isz C

WhileEnd

If U>12:Then Isz V:1→U:IfEnd
Locate U,V,"<END>"
====================
最新記事
検索フォーム
最新コメント
カテゴリ
C# (3)
Visitors
Online Counter
現在の閲覧者数:
プロフィール

やす (Krtyski)

Author:やす (Krtyski)
since Oct 30, 2013


プログラム電卓は、プログラムを作って、使ってナンボ!

実際に触って気づいたこと、自作プログラム、電卓プログラミングについて書いています。

なお管理人はカシオ計算機の関係者ではなく、Casio Basicが面白いと感じる1ユーザーです。


写真: 「4駆で泥んこ遊び@オックスフォード郊外」

リンク
月別アーカイブ
Sitemap

全ての記事を表示する

ブロとも申請フォーム

この人とブロともになる

QRコード
QR