Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2009-02-03

どんな素数でも一瞬で素因数分解する方法

きっかけ:

NANKI Haruo: どんな素数も一瞬で素因数分解できるようになる壷、売ります。

ライブドアでアンケートを作成してTwitterで告知: どんな素数でも一瞬で素因数分解する方法 - livedoor リスログ

結果:

自信満々で「無理無理www」と言っている人が23.7%もいるけど、どんな素数pを素因数分解しろと言われてもpって返事すればいい。素数pはすでに素因数分解済みなのだから。


「素数はそれ以上分解できない」という意見がいくつかありました。となると「分解」の定義が重要になってきますね。岩波数学事典第3版によれば(p.469)

180 C. 素因数分解

正の整数aは素数の積に分解することができる。かつその分解の結果はただ1通りである。…

とのこと。「分解」という言葉の定義は書かれていませんが「正の整数aは素数の積に分解することができる」ということは、素数であっても1であっても素数の積に分解できるということ。つまり「素数は1個、1は0個の素数の積に分解される」という意味に取るしかないんじゃないかなと思います。もっと信頼できる書籍で「いや、そう解釈するのは間違っている!」と主張できる根拠があればご連絡ください。

aa 2009/02/03 21:48 結論から、1は素数ではありません。だから上記の命題が導かれます。もっと勉強しましょう。

idadiidadi 2009/02/03 23:11 >どんな素数も一瞬で素因数分解できるようになる壷
素数以外を入れたらどうなるんですか?その壷

MarriageTheoremMarriageTheorem 2009/02/04 01:13 >idadiさん
入れられた物を(それが何なのかは気にせずに)そのまま返すようにすればよいのでは?
「素数を入れたら素因数分解の結果が返ってくる」という仕様は満たしていますし。

testtest 2009/02/04 10:30 数学的にいうと、分解できる=factorizeできるということですね。Google scholarでprime numberとかfactorizationとかいれたらいっぱい定義でてきますよ

shivashantishivashanti 2009/02/04 10:52 一つ以上の素数の積で表せば良いから「どんな素数pを素因数分解しろと言われてもpって返事すればいい。」だよね。
で、1は素数じゃないから無視してOK。

ただし、「1は0個の素数の積に分解される」これは間違い。
一意性が無くなってしまう。

hajimehoshihajimehoshi 2009/02/04 11:48 > ただし、「1は0個の素数の積に分解される」これは間違い。
> 一意性が無くなってしまう。
なぜですか?

shoushou 2009/02/04 18:04 2^0 * 3^0 .... とか言いたいのか?

wd0wd0 2009/02/04 19:46 類似品として、どんな上昇列でも一瞬でソートできるようになるお鍋、いかがですか。

hyukihyuki 2009/02/10 21:05 テトラ「そ、そんな方法があるんですかっ!」→2
ユーリ「ユーリにもできるにゃ」→1

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証