次の関数について考えます。 これをそのまま書くと、kはnまでで十分だから、 def H(n): return sum(n / k for k in xrange(1, n + 1)) ですね。O(n)の計算量のはずです（nが小さければ）。 さて、この計算を速くできないでしょうか。まず、n = 10で具体的な…

Problem 375で使われている擬似乱数は sn+1 = sn2 mod d ここで法dはd = pqでpとqは4n+3型の素数です。これをBlum-Blum-Shubというそうです。 知りたいのはこの数列が戻ってくるかです。まず、初項に戻ってこないかもしれないのは当然です。自乗の剰余になれ…

昨日、アルゴリズマーのためのゴルフのススメを読んで、帰宅ジョグのときに最初の問題を考えた。そういえばProject Eulerにもこんな問題あったなあ。でも前は解ければいいってことでO(n2)にしっちゃったのかなあ。こういうのってO(n)ってわかってると思いつ…

Pythonで何も考えずにエラトステネスのふるいのコードを書くとこんな感じでしょうか。 def sieve(max_n): a = [ True ] * L for p in takewhile(lambda n: n * n < L, (n for n in xrange(2, L) if a[n])): for k in xrange(p * 2, L, p): a[k] = False Bool…

例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。このようなときは、適当に上限を…

エラトステネスのふるいです。ふつうに書いてみます。 def sieve1(N :Int) :List[Int] = { val a = new Array[Boolean](N + 1) for(n <- 2 to N) a(n) = true for(p <- Iterator.range(2, N + 1).takeWhile(p => p * p <= N) if a(p); k <- Iterator.range(p…

Pythonと同じことをします。 まずは試し割りから。 def is_prime1(n :Int) :Boolean = Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0) def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] = Iterator.range(2, N + 1).fi…

エラトステネスのふるいの速度を確認します。まずは最も単純なもの。 def sieve1(N): a = [ True ] * (N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])): for k in xrange(p * 2, N + 1, p): a[k] = False return [ n for n…

昨日ひどかったので考え直してみました。要するに試し割りの回数がわかればいいのです。もちろんわからないので、n前後の試し割りの回数の平均を求めます。ガウスの故事に倣って1000個ずつ取って平均します。なるべく長いスパンで見たいので、平均を取る範囲…

どの素数判定法を使うべきか迷うことがあるのでまとめてみます。 試し割り法 ある整数が素数であるか2から順に割っていきます。nが素数かどうかの判定には√nまでの素数で割り、全て割り切れなかったら素数です。途中で割り切れたらその時点で合成数と分かり…