N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
フィボナッチ数を計算する方法をまとめてみた - yattのブログ
Project Eulerで巨大な数のフィボナッチ数(10^14番目ぐらい)の剰余を求める必要があったので、関連するアルゴリズムについてまとめました。行列を使った最適化については@nico_shindanninさんにヒントをいただきました。 定義通り求める すぐに限界のくる方法。一度の関数呼び出しで2度再帰することと、同じフィボナッチ数を何度も計算するので時間がかかる。 def fib_naive(n): if n in [0,1]: return 1 else: return fib_naive(n-1) + fib_naive(n-2) メモ化して求める ナイーブな方法より計算が減るので速くなるけど大きなフィボナッチ数を求めようとするとメモリをバカ喰いする。 def fib_memo(n, m={0:0,1:1}): if not n in m: m[n] = fib_memo(n-1
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
M.Hiroi's Home Page / Lightweight Language
