SICP#3まとめ 補足
SICP#3まとめ vol2の補足です
hogelogさんとumeajiさんにコメント頂きました!
とっても嬉しかった&私なりにいろいろ考えた事などを書きたいと思います
hogelogさんのコメント
> 処理速度かなぁ?? yep. 日本語SICP手元に無いんで原文で示しますけど ”The end test for find-divisor is based on the fact that if n is not prime it must have a divisor less than or equal to (sqrt n). This means that the algorithm need only test divisors between 1 and (sqrt n).” http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6 日本語版だときっと「nが素数でなければ除数は1とnの平方根の 間にある」とか書いてますよねきっと。言いかえると 「nの平方根+1からnまでの間には除数は無い」ということですよね。 そんなことをふまえてこの日記に示した記録を眺めてみましょう。 「必死に探してるwwwwww無いのにwwwwww」と笑えたらゴールです。
うーん。。。
余計な部分の計算を省いて計算速度を速くするためのコードがあれ??
■■素数の場合除数は1とnの平方根の間にない■■というのは簡単に言い換えると
素数は自身が除数となるので合成数のように1とnの平方根の間に
因数はないですってことを言いたいのかなぁ??
ちゃんと分かってないかも(p>□<q*))
umeajiさんのコメント
n をかけ算 a * b で表すことを考えたとき、a が大きくなるにしたがって b は小さくなっていきますよね。ちなみに、b にも同じことが言えます。 a と b が一番大きくなる値はいくつかってことを考えると √n になることがわかると思います。 このことから除数は 1 から↓√n↓(↓は切捨て)の範囲に 収まることがわかります。 つまり、↑√n↑(↑は切り上げ)から n の間には除数は存在しません。 n = a * b で表されるとき、a と b は両方大きな値になることが 出来ないことを思い出してください。 要するに、hogelog さんのとおりです(汗)。 先の方法では √n が整数になるときに困るので、常に切り下げ をしたほうが良いです。 書き直すと「(↓√n↓ + 1) 〜 n の範囲には除数は存在しない」 となります。
■■a と b が一番大きくなる値はいくつかってことを考えると、√n になることがわかると思います。■■
ココどうしてか分かりませんでした(´∩`。)
なのでちょっと実数を入れてみました
n = a*b
n = 8 とした時
整数だと 8 = 2*4 またはこの逆ですよね
この場合でaとbが共に最大になる数値を考えたらいいので2√2ですよね?
√nまではなんとか理解出来ました
nを割る数字(除数)は1と√nの中に収まるというのは
100の因数を考えた時に2.4.5.10.20.25.50となるけれど
計算としては10まで分かったら20.25.50は計算出来たのと同じ
という事と同様の理解でいいでしょうか??
なので合成数を省くためのコードとの認識であってますか??
■■先の方法では √n が整数になるときに困るので、常に切り下げをしたほうが良いです。
書き直すと「(↓√n↓ + 1) 〜 n の範囲には除数は存在しない」となります。■■
√nが整数の場合どうすればいいのか考えていたので参考になりました!
ここに至るまでにいろんな方にいろいろ教えて頂きとても参考になりました
正直ブログを書いてみたものの自分の認識があってるかどうかも自信がありません
突っ込みどころ満載かもしれませんがその際は是非ご鞭撻をお願い致します
ちゃんと理解出来るように頑張りますのでこれからも宜しくお願いします