その数の約数を求めるには、素因数分解をするしか手はありませんか？素因数が17とか19位までならなんと

その数の約数を求めるには、素因数分解をするしか手はありませんか？素因数が17とか19位までならなんとかやってもいいのですが、それ以上大きなものになると時間がなくなってしまうので飛ばしてできないことになってしまいます。

約数を求める裏技みたいな定理、また素数の判定法があれば教えていただきたいです。

多少マニアックな話になっても構わないので、よろしくお願いします。

質問者からの補足コメント

• その数じゃなくある数でした。失礼しました。

    補足日時：2019/01/19 18:09

• 何度も補足すみません。
  実際に解いていた中でできてたのは13333を素因数分解しないと解けない問題でした。答えを見ると67で割れるのですが、皆様の回答から、地道にやるしかない、しかし67まで試すのは時間がかかりすぎるのでこの問題は諦めるしかない、解かなくていいということになりますか？

    補足日時：2019/01/20 08:18

No.9 ベストアンサー 回答者： Tacosan 回答日時： 2019/01/20 23:36

具体的にどのような問題なのかわからないので「この問題は諦めるしかない、解かなくていい」かどうかは判断できない.

もっといえば
あなたが「13333を素因数分解しないと解けない」と思い込んでいる
という可能性が排除できないよね.

この回答へのお礼

アドバイスありがとうございました！
回答者さんの回答から、確かにそもそもこれを解かないといけない訳じゃないと考えると、正解にたどり着くことができました！
ありがとうございました。

お礼日時：2019/01/22 16:14

No.8 回答者： t_fumiaki 回答日時： 2019/01/20 13:52

√13333<116 なので115までの素数を調べれば良いので、地道に試す。

999975を素因数分解する問題じゃないですか？
3×5×5×13333までは簡単。
そこまで書けば0点では無いと思います。

この回答へのお礼

ご存知でしたか！
確かに途中式で部分点がもらえるかもしれないので頭に入れておきます。
ありがとうございました。

お礼日時：2019/01/22 16:15

No.7 回答者： tknakamuri 回答日時： 2019/01/20 12:35

そのなに大変ですか？

67って19番目の素数ですが
2桁の数は九九を覚えていれば則素数か
どうかわかりますからたいした手間じゃない。

それでも手間が掛かりすぎるということなら
捨てるしかありませんね。

この回答へのお礼

ありがとうございます。

お礼日時：2019/01/22 16:16

No.6 回答者： springside 回答日時： 2019/01/20 09:52

13333=67*199を手でやる必要があるとすれば、それは地道に計算していくしかないね。

だからといって、そこまでやって解くべきか、または解かなくていいか、はあなたの判断であり、他人に聞くべきことではない。

この回答へのお礼

語弊が生じてしまい申し訳ございません。わたしは皆さんなら捨てるかという意味で質問をしたつもりでしたが、説明不足でした。ご回答ありがとうございます。

お礼日時：2019/01/22 16:17

No.5 回答者： Tacosan 回答日時： 2019/01/19 23:50

「素数かどうか」を判定するだけなら「簡単」だけど, 「因数を見付けろ」というのは別の話. これが「簡単」にできるようだと, いろいろ困ることになるかもしれない.

まあこの場合対象とするのは 1000桁とかの数字だけど.

この回答へのお礼

それは聞いたことがあります。リーマン予想が証明されると世界が終わるとかなんとか…(よくわかりませんが笑)
とにかくご回答ありがとうございました。

お礼日時：2019/01/22 16:19

No.4 回答者： tknakamuri 回答日時： 2019/01/19 23:49

どの程度の大ききの数ですか？

整数n(>0)の素因数は√(n)以下ですから、

例えばー万以下の数なら
100以下の素数、つまり15個の素数で試すだけです。しかも、
2、3、5は割らなくても割りきれるか簡単にわかります。

千以下なら、2、3、5、7、11、13、17、19、23、29、31 を試すだけ。


一つ素因数が見つかれば、それで割った数が別の素因数を探す対象ですから、
試すべき素因数はあっというまに減って行き、
結局たいした計算量にはなりません。

任意の大きさの数が対象の場合、素因数分解の近道は見つかっていません。
有れば、RSA暗号は安全では無いということになるので
見つかれば情報化社会のセキュリティが崩壊し、社会の大混乱が
おきるでしょう。マジで・・・

この回答へのお礼

残念ながら(そうでもないのかな？)地道にやるしかないのですね。ご回答ありがとうございました。

お礼日時：2019/01/22 16:20

No.3 回答者： springside 回答日時： 2019/01/19 19:13

素数の判定法は山ほどある。

↓
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0 …

この回答へのお礼

ありがとうございます。調べてみます。

お礼日時：2019/01/22 16:20

No.2 回答者： kairou 回答日時： 2019/01/19 19:05

最大公約数を求めるならば、「ユークリッドの互除法」と云うものがあります。

多くの解説がありますから、ネットで調べて下さい。
最大公約数で割れば、数は小さくなりますから、分かり易くなります。
勿論、最大公約数が 1 ならば、お互いに素と云う事ですが。

この回答へのお礼

少し調べましたが、便利な方法ですね。ご回答ありがとうございます。

お礼日時：2019/01/22 16:21

No.1 回答者： t_fumiaki 回答日時： 2019/01/19 18:32

2,3,5,7,11,13・・・と地道になるしか有りません。

n番目の素数を表す式を、人類は未だ作れていません。

素数の判定法
実用上は先ず無理ですが、ウィルソンの定理で判定は可能。
(n-1)! +1がnで割り切れたら、nは素数

この回答へのお礼

そんな判定法があるんですね！
ありがとうございます。調べてみます。

お礼日時：2019/01/22 16:12