素因数分解をするプログラム(aのb乗は表示出来なさそうだからa×…×aでもいいけど)を作りたいけど、どうやって、ああいうのを計算(?)させたらいいんですか？ (文章複雑orz)

aのb乗:pow(a,b) がありますぞい。

したいのは素因数分解ですぞ(^ω^;)

トピの趣旨とそれてしまいました。 素因数分解については自分の知識ではわかりません。 助けになれずすみません。

今意味がわかりました。 aのb乗はa^bで表記できますよ。 キーボードをシフトすれば出てくるはずです。 (話題がそれててすみません)

素数ぅ…(^ω^#)

なるほど～ 残るは素因数分解を行うプログラムか…

学校で習った通りの、自分が手でやるのと同じやり方でまぁ5桁くらいまではいけるんじゃない？ 割りきれる素数を順に探して割っていく感じで 60桁とかなると少し問題あるけど。

作ったことあるんですが自分で作ってみた方が勉強になりますよ。 ・INPUTで数字を受け取る ・2から目的の数字の半分までループさせる ・数字を割って余りがでない場合は同じ数字でやり続ける、割った後の数字は取っておく ・あまりが出たらループを進める ・最後の余りも必要 配列に割り続けた際の数字を保存しておけば素因数分解あがり。 DIM,FOR～NEXT,WHILE～WEND,IF～THEN,DIV,MODを使えば作れると思います。必要ならINPUTも。

ありがとうごさいます！ やってみますね！

素因数分解するときは、まず最初に素数を求めておくとよいです。 素数を求める方法は、大きく分けて (1)小さい自然数から順番に１つずつ、素数かどうか確かめていく方法 (2)エラトステネスのふるいで、ふるいにかける方法 の2種類がありあす。 学校で教えてくれるのは(2)の方法かなー？ やってみるとわかりますが、(2)が圧倒的に速いです。そのかわり、(1)よりも沢山のメモリが必要で、かつ、あらかじめ求る素数の上限も設定しておかなければいけません 私はこれを比べてみてはじめて、処理速度と消費メモリはトレードオフの関係にあることを実感しました(゜◇゜)

どうすればいいですかね…?

素数を求めるのは私か説明したやり方をつくってからでも大丈夫ですよ。

うんうん まず、あきとさんの方法でやってみましょう(*´∇｀*) 私が書いた（1）の方法は、ほぼあきとさんが書かれた方法と同じです

素数を求める式は未だ見つかっておらず、本当に難しいです。だから、与えられた数より小さい自然数すべてについて素数かどうかを調べさせるプログラムにすれば、大きなケタになっても対応できます。具体的にいくと 与えられた数をAとする。素数とは、「1とその数でしか整数で割りきれない数」⇔「その数以外の全ての自然数で割ると、いずれについても整数部分×それ以外の数がもとの数に一致しない」が成り立ちます。よって試行回数は多いですが、FOR～NEXTを利用してこの方法をとるのが最良でしょう。 僕の表現力が足らずもうしわけないです。いつかプログラムの形にします。

むしろなぜ素因数分解したいのか知りたいです!! そ・す・う!! そ・す・う!!

「そこに合成数があるから( ￣▽￣)」 ・・・じゃないですね(´･ω･`)

夏休みの宿題

気になったから…ですかね(笑)

夏休みの宿題にしても多くて6問くらいしかないですよね… これは面白いお題なので頑張ります

なんだ宿題じゃないのか・・・ガクッ まあ照れてそう書いただけかもですね。 たった 6 問の素因数分解を解くために、 (普通にやれば 10 分で終わるところを) 数時間かけて素因数分解プログラムを書く もしそうなのであれば、優れた hacker になれる可能性高いです。 全力で応援したいww

「楽をするためならどんな苦労もいとわない」 ですね(≧∇≦)b

'ここから先は自分が書いたコードを書きました。汚いのであしからず。 def primes(n) var i,r$ if n<4 then return format$("%d",n) 'sqr(4)がforが働く最小値だから for i=2 to sqr(n)'えらとすてねすのふるい if n mod i == 0 then while n mod i == 0 '割りきれた inc cx n=n/i wend if cx>=2 then r$=r$+format$("*%d^%d",i,cx) else r$=r$+format$("*%d",i) endif next var junk$=shift(r$):return r$:end

素数に規則性が発見されてないからどうしても素因数分解に限界がでてきますね･･･

リソースさえあれば限界はないと思う 現実的な時間ですむかどうかは別として

というか60桁って自前で桁落ちしないようにするしすてむいるくね

まあ、素数は謎が多いですからね… (^ω^#)<ｷｿｸｾｲ…

みなつさん それですそれです!! エメラルドさん 素数に興味あったら、「リーマン予想」とか調べるといいかも。 全ての自然数と全ての素数とを結びつける「ゼータ関数」というのがあるんですよ

皆さん数学が好きそうですね! 僕の学校では数学好きな人あまり居ないっぽいんですよね…

MIKIさん» その『ゼータ関数』って「複素数」についてなのでは？ (複素数は『a+bi(iは虚数)』で表せる「存在しない」数、素数は「存在する」数) 違っていたらすいません…

一応僕が作ってみた自然数が素数かを判別するプログラム↑ これ使えませんかね？

ちょっと待った～!!! 複素数は「存在しない」数ではありません。 まず、実数は数直線で表せるってのはいいよね? 確かに(実数を除く)複素数は「数直線上で表せない」です。その通り。 でもここにもう一本数直線を持ってきて、元の数直線の原点に直交させます。 するとおなじみのxy平面ができあがりますね。 そこで、複素数のaをx軸に、bをy軸に当てはめると、a+biをxy平面上の一点で表すことができます。これが複素数の表し方(のひとつ)。 このときxy平面のことは「複素数平面」と呼び、x軸を「実軸」、y軸を「虚軸」と呼びます。 なおこの点は、原点からの距離rと角度θでも表すことができるので、aとbの代わりにrとθで複素数を表すこともあります(むしろこっちのが有用)。 このθはみんなの好きなatanを使ってθ=atan(b,a)で表せるのよ!

そのプログラムでいいと思います。ただし 1 は素数でも合成数でもないので、2以上の自然数を入力させるのがいいでしょう。

リーマン予想の話になるとゼータ関数は複素数を扱いますが、 「全ての自然数と全ての素数の対応」という範囲では、実数しか使いません。 つまり、 ゼータ関数 ζ(s) = 1/(1^s) + 1/(2^s) + 1/(3^s) + ... (sは自然数) が、 オイラー積 = 1/(1-1/(2^s)) * 1/(1-1/(3^s)) * 1/(1-1/(5^s)) * 1/(1-1/(7^s)) * ... という感じの、全ての素数 p についての 1/(1-1/(p^s)) の積に等しくなるというわけなのです。

す…凄い… 確かにそうでしたね…(・・;) じゃあ、それをどう利用すればいいんでしょうか？

利用できません (キリッ!

え…?(困惑) まあ、何かに使える可能性は0ではなさそう…? (。∀°)<ｾﾞｰﾀｶﾝｽｳｩｩｩｩｩ(ry

結局素因数分解はできました？ 配列に素数残す処理が必要かなと思ってましたが

そう言えば確かに… どうやればいいですかね？

上に書いてた方法をそのまま書いてみるのがいいですよ。素数判定のソースは見たのであれだけ書けてれば大丈夫。 まずはMODを使って余りがでない約数をプリントしてみましょう。最後に残った数字もプリントすればできるはずです。 たとえば60なら2 2 3 最後に5となるはず。

あﾞｧﾞｧﾞｧﾞｧﾞ!! なんかいい感じかな？と思っていたら表示されたのが素因数が1回ずつ(100なら2と5が1つずつ)しか表示されない…! どこがちがっているんでしょうか？

↑は26行目のP→Xに直したらうまく表示出来ました！ «おまけ» 最後のところに 『Aボタンを押したらもう一回、Bボタンを押したら終了』ってのを追加したいんですけど、 それは、どうやって作れますか？ (なんかDIALOGとか使ってもできた気がするけど、ロマンが欲しいから(笑))

WHILE 1 B=BUTTON(2) IF B==#A THEN GOTO @TOP IF B==#B THEN END VSYNC WEND FLOOR(B/A)はB DIV Aで同じ処理になりますよ。小数点を考慮しない割り算という事です

皆さんのおかげで配布することが出来ました！ もしよかったら使ってみてください！

※公開キーは別の投稿に書いてあります