• ベストアンサー
  • 困ってます

素因数分解!?

xは自然数でx^2=736164のときxを求めよ。という問題なのですが、素因数分解してくと2、2、3、3の順で分解できるのはすぐ気づきます。しかし20449でとまってしまいます・・。なんとか143で分解できると気づいてx=858と答え出せたのですが、もっと上手い解き方ありますか?あるいは、2~3桁の素数の積を一瞬で見分ける方法はありますか?わかる方いましたらお願いします。

共感・応援の気持ちを伝えよう!

  • 回答数5
  • 閲覧数601
  • ありがとう数6

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.2
  • TK0318
  • ベストアンサー率34% (1261/3651)

基本は元の数の√の値ぐらいまでの素数を順に試していくしかありません。 ただし 2の倍数・・・1の位が偶数 3の倍数・・・すべての桁の数を足すと3の倍数 5の倍数・・・1の位が0か5 は見分けやすいです。 736164の場合 →2×368082 →2×2×184041 →2×2×3×61347(一番小さい素数の2では割れないのでその次に小さい3で割ってみる) →2×2×3×3×20449 ここで20449を小さい素数から順に割ってみると3無理、5無理、7無理、11で割れるので →2×2×3×3×11×1859 →2×2×3×3×11×11×169 169=13×13より →2×2×3×3×11×11×13×13 とにかく2から素数で順に割って割れるかどうか確認してみるのが一番早いです。コンピューターも現在のところこの方法しか無理みたい立ったと思いますので王道ですがこの方法が一番いいです。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

やっぱり小さい素数から割れるか考えていくしかないということですね!ありがとうございました。

その他の回答 (4)

  • 回答No.5
  • alphion
  • ベストアンサー率19% (27/136)

ルートの計算方法をご存知ですか? 与えられた数字を下の桁から2桁づつ区切る 20449 => 2 04 49  1    1  4  3 +1    ------- --    2 04 49  24   1        <= 1x1  2に一番近くなるa^2のaは1 + 4   ------- ---   1 04  283    96     <= 24x4   104に一番近くなる((a+a)x10+b)xbは、    3  ------- ((1+1)*10+b)xb で、b=4          8 49          8 49  <= 283x3   849に一番近くなる… =3          ----             0 この知識を使って、一番左の数が2なので、2以下で最大になるa^2の答えは1だから、一番上位は1 小数が出ないなら、c^2の下1桁の値は与えられた数字の下1桁に一致する から、下1桁が9になるのは、3か7 というように絞れば良いのでは?

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ルート計算法なんて初めて聞きました。これから調べてみます。ありがとうございました。

  • 回答No.4
  • ctrlzr
  • ベストアンサー率29% (18/62)

logを使用します。 x^2=736164 logx^2 = log736164(底は10) 2logx = 5.866974576 logx = 2.933487288 x=10^2.933487288 = 858

共感・感謝の気持ちを伝えよう!

質問者からのお礼

関数電卓か何か使用可なら対数で考えることもできますよね、ありがとうございました。

  • 回答No.3
noname#16614
noname#16614

普通の試験等で見かけるのはせいぜい19程度までなので、素因数分解をする時はたいてい19までのチェックをしてから、なければ終了ということにしています。 20449というのは、チェックしてみると11で割り切れます。 また、20449÷11=1859となり、この1859も11で割れます。 1859÷11=169となり、169は13の二乗ですね。 以上のように、二桁の大きい数字及び100を越えるような素因数分解で問題がでることはまずありません。 なぜなら、ある程度原理が分かっているなら、そこまで面倒くさいことをして素因数を求めさせる意味が無いからです。 ただ、面倒くさいことをさせる問題は全くない、とは言い切れませんのでご注意を。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

素因数分解で3桁を越えることなんてないですよね、自分は143=11X13てこのとき気づきませんでした・・・。ありがとうございました。

  • 回答No.1
  • Josquin
  • ベストアンサー率30% (771/2492)

一瞬で見分ける方法はありません。数の大きさから範囲を絞り込み、順番にあたっていくしか無いと思います。 桁の大きな素数の場合はコンピュータを使っても何年もかかる可能性があり、暗号に使われるぐらいです。 http://www2.ocn.ne.jp/~mint905/fhpstory/ango.html

参考URL:
http://www2.ocn.ne.jp/~mint905/fhpstory/ango.html

共感・感謝の気持ちを伝えよう!

質問者からのお礼

素数が暗号に使われているなんて初めて聞きました。ありがとうございました。

関連するQ&A

  • 素因数分解の問題

    「1から30までのすべての自然数の積をXとすると、Xの末尾には0がいくつ並ぶことになるか。なお、Xは29以下のすべての素数の積、X=2a×3b×5c×7d・・・×29で表される。」という問題があります。解説の、「10を素因数分解すると2×5であるから、末尾に並ぶ0の個数nは、Xのすべての素数の積 X=2a×3b×5c×7d・・・×29 において、aとcの内大きくない方である。」という記述が理解できません。どなたか教えてくださいませんか?

  • 素因数分解について

    X=√4,840,000 を素因数分解?? で解く場合、100*2*11=2,200 となると思いますが、素数の100を1000にしては駄目ですか? そもそも、素因数分解のルールが理解出来ていません。 素因数分解の簡単なやり方を分かり易く教えて下さる方、宜しくお願いいたします。 因数分解は方程式なので、取っ付きにくいイメージがあります。

  • 素因数分解 解き方

    素因数分解 解き方 120=2X2X2X3X5  ←どうやってこの数が出てきたんですか? 3 =2 x3x7ってどうやったらこうなるんですか?  今、素数をマスターできましたが素因数分解はまだです。   詳しくお願いします!

  • 素数の素因数分解

    素数(例えば17)の素因数分解について  (1)すでに素因数分解は終わっている (17の素因数分解は17)  (2)素因数分解はできない のどちらの見解が正しいですか?

  • 素因数分解について

     ものすごく大きな素数二つを掛け合わせた数を素因数分解することは難しい、というようなことを本で読みました。 これって暗号を作ることにも利用されているみたいですが、どうしてこの数を素因数分解することが難しいのでしょうか?

  • 素因数分解をこの問題でどう使うのか??

    問題 「a、b、cは自然数とする。 2^3a×3^2b×5^cで表せる6桁の数があり、その中央の4桁は0736であることがわかっているとき、a,b,cの値を求めよ。」 これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。 ~私の解法(素因数分解の利用なし)~ 3^2b=9の倍数なので、9の倍数の性質と2×5=10を利用して6桁の数が「207360」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも9の倍数の性質を知らないと解けない問題自体見たことがありません。 素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。

  • 素因数分解について

    中学三年で習う素因数分解についてです。 素因数分解をするときに、数字を最小の素数で割らなければいけない理由は何ですか? また、素因数分解を利用して最大公約数と最小公倍数を求めるための式(共通の素数をかけていくという式です)の意味が理解できません。。 何故あの式で最小公倍数と最大公約数が出るんでしょうか? テストが近いのでかなり焦っています。 どなたか詳しく説明してくださる方、回答よろしくお願いします。

  • 素因数分解でわからない問題があります。教えていただ

    けますでしょうか。 勉強していて、下記の問題がどうしてもわかりません。 解答はついているのですが、考え方がわかりません。 教えていただけないでしょうか? 問い 56にできるだけ小さい自然数をかけて、ある整数の二乗にしたい。どんな数をかければよいか? 素因数分解はできるのですが(2の3乗X7)、その後の考え方がわかりません。 ちなみに答えは2X7=14 です。 解説に、56=2の3乗x7=2の2乗x(2x7) よって、2x7=14とありますが、 この解説がまったく理解できません。 2x7=14が何を意味するのかがわかりません。 どう考えればよいのでしょうか? 同じく 360を自然数でわって、ある整数の2乗にしたい。どんな数でわればよいか? という問いも、素因数分解から先の考え方がわからず、解けません。 (答え10,40,90,360)。 どなたか 解き方(考え方)を教えていただけますでしょうか。

  • 素因数分解

    1、 216を出来るだけ小さい自然数でわって、ある整数の2乗になるようにしたい。どんな自然数でわればよいですか? 2、 504に出来るだけ小さい自然数をかけて、ある整数の2乗になるようにしたい。どんな自然数をかければよいですか? この問題を素因数分解を使って解くようなのですが、、、、、 わかる方いましたら教えてください。 よろしくお願いします。

  • 素因数分解の証明問題

    素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、 φ(n)=n{1-(1/p_1)}{1-(1/p_2)}・・・{1-(1/p_r)}となることを示せ。 ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。 よろしくお願いします。