2016-06-05

n以下の素数のsumを高速に計算する

動機
問題概要
準備
計算量
- \(1 \le p_b \le n^{1/4} \) の時
- \(n^{1/4} \le p_b \le n^{1/2} \) の時
素直なプログラム
最適化したプログラム
余談

動機

Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler

この問題は2*10⁶以下の素数の合計を求めるだけなので簡単なのですが、Lucy_Hedgehog さんという方が面白いアルゴリズムをpostしていました。

せっかくなので、なるべく初心者にも分かりやすいようにアルゴリズムの概要を説明したいと思います。アルゴリズムとか計算量とかどうでもいい人は、

optimized_prime_sum.cpp · GitHub

のプログラムをコピペして使って下さい。

問題概要

競技プログラミングで以下のような問題が出た場合、どう実装すればいいでしょう？

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 10⁶

エラトステネスの篩を使えばn以下の素数の列挙は \( O(n \log\log (n)) \) で出来るので、このアルゴリズムで十分だと思います。

では次の制約の場合はどうでしょうか。

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 10¹²

答えは 64bitに収まらないので、10⁹ + 7で割った値を答えて下さい。

アトキンの篩を使えば計算 \( O(n / \log\log(n)) \) , 空間 \( O(n^{1 / 2}) \) で計算出来る(らしい)ので、これで十分かも知れません。が、今回は計算 \( O(n^{3/4}) \), 空間\( O(n^{1 / 2}) \) で計算出来る方法を紹介したいと思います。

2015-09-29

ISUCON5 オンライン予選通過しました

優勝賞金100万円！今年もやります ISUCON5 開催と日程のお知らせ #isucon : ISUCON公式Blog

「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。

...

ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。

ISUCON5オンライン予選に参加してきた « chibiegg日誌

ということで参加してきました。

チームマウント竹田氏(メンバー: @misodengaku, @chibiegg, @__math) で出ていました． 16位で予選通過です。いつもは @aki33524 も参加するんですが、上限が3人までということだったので、裏番組のTrend Micro CTFを頑張ってもらいました…、きひろくんごめん。

他のメンバーの参加記です