No.3ベストアンサー
- 回答日時:
全部調べる.基本はこれしかない.
素因数分解は素数の約数(素因数)が分かって初めてできるのだから
素因数分解してから素因数を求めるというのは本末転倒.
ただ,全部調べるといっても
馬鹿正直に2から2613まで全部調べるのはやりすぎで
実際は
2から(2613)^{1/2}(2613の平方根のうちの正の方)までの
整数で素数であるものを順番に調べればいい.
そして,その範囲の整数が素数であるか一つ一つ調べるのは無駄で
先に,必要な範囲の素数をエラトステネスの篩で調べ上げておくとよい.
そうするとそれなりの速さで素因数分解はできる.
コンピュータで計算させるときはこんな方法でざっくりやってしまう.
これくらいなら慣れてれば,30分くらいもあればプログラムできると思う.
#個人的にはこの手のプログラムはHaskelで書くのがよいと思う.
人間がやるなら,直観もあるから
思いついたらそれらしい数でやってみるというのは
まさに王道.
No.5
- 回答日時:
「全部調べる」とは言っても、もし2613を割り切る素数が存在するのなら、そのうちで最小のものは√(2613)=51.1… 以下です。
だから、51より小さい素数だけ、つまり高々十数個の素数pについて調べれば、素因数が(もしあれば)見つかることになります。
一般に、ある数nについて調べるには、√n以下の素数で割り切れるかどうかを調べます。
(1) もしどれでも割り切れなかったら元の数nは素数です。
(2) もし割り切れる素数pが見つかったら、その商(つまりその割り算の答)qが√q以下の素数で割り切れるかをどうか調べます。
これを繰り返せば良いのです。
nがあまり大きな数でなく、また√n以下の素数の表を持っているのであれば、実際上、大した手間は掛かりません。しかしながら、nがたとえば何十桁という大きさになると手計算では到底やってられません。さらに大きくなると、コンピュータでも手に負えなくなります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 大学・短大 〈至急〉関西大学社会安全学部か立命館大学政策科学部のどちらに行くかとても迷っています。 3 2023/02/11 21:47
- その他(結婚) 【長文】結婚したい彼と性欲も無く結婚もしたくない私 7 2022/10/20 23:30
- 数学 どうか教えてください。 4 2022/07/02 20:18
- 数学 教えてください。 2 2022/06/30 14:26
- 数学 【 数I 集合の要素の個数 】 問題 1から100までの整数のうち,6と8の少 なくとも一方で割り切 2 2022/07/18 12:51
- 数学 「素数(数の原子)」とは、「1と自分自身以外で割り切れない正の整数」でしたよね? 1 2022/04/09 23:45
- 中学校受験 42を割っても、54を割っても割り切れる整数のうちもっとも大きい整数はいくつですか。 またそのような 5 2022/09/22 15:29
- 数学 「素数」とは、「1と、それ自身でしか割り切れない数」。 「素因数分解」も「素数」の仲間ですか? 3 2022/04/14 22:45
- 数学 命題 nが合成数ならば、√n以下の素数pが存在し、pはnを割り切る の対偶を考える際、nが合成数なら 1 2023/05/23 00:24
- 数学 この解法があっているか分からないので教えてください 4 2022/07/12 14:59
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
自然対数Ln(x)からxを求める方...
-
1/3乗などの計算方法
-
逆関数の求め方
-
0から1になった時の増加率を教...
-
9X2乗-6X+1 はどうやった...
-
改良土のCBR
-
時定数の計算を教えてください
-
数Ⅰの実数の問題について教えて...
-
分数式の計算で答えがこうなっ...
-
中学 数学 こういう問題の時答...
-
20〜200までの自然数の和
-
イコール
-
小学生の算数:何通りかの計算
-
不定積分の答えをどこまで出す...
-
数学 ∑(1からnまで)1/k2乗...
-
(X-4)(3X+1)+10 この式を因...
-
Mathematicaで恒等式を解く方法
-
漸化式での次数下げ
-
1/1+1/2+1/3+...+1/100
-
中学数学 a※b=1/3(a+b)とする...
おすすめ情報