@kagamiz (Jayson Sho Toma)

Presentation on theme: "@kagamiz (Jayson Sho Toma)"— Presentation transcript:

1 @kagamiz (Jayson Sho Toma)
講義 1: 素数と累積和 @kagamiz (Jayson Sho Toma)

2 素数とは？ 1 とその数自身以外に約数を持たない数 ただし 1 は素数ではない なぜか考えてみよう 素数ではない数を合成数という

3 素数判定 数 n が素数かどうか判定したい 試し割りをしていく方法 素数の性質を使う方法 最悪 n に比例する時間がかかる

4 素数判定 数 n が素数かどうか判定したい 試し割りをしていく方法 素数の性質を使う方法 √nまでの素数で試し割りを行う
何故これでいいのか？

5 √n までの試し割り：証明 n が合成数であれば, 定義より n = a × b と表せる.
いま a ≧ b ⇒ a × b ≧ b × b = b^2. よって n ≧ b^2, √n ≧ b となり, √n 以下の約数があることが証明された.//

6 実行時間とプログラムの計算量 ループの回数が大体 10^8 (1 億) で 1 秒 10^9 回の処理は約 10 秒程度かかる!
10^8 回以下程度の処理を心がけよう 詳しい話は「計算量 オーダー記法」で 　ググる or 先輩達に聞こう

7 素数の個数を数える 区間 [l, r] の素数の個数を数えよう! [l, r] の素数を試し割りで毎回数えると,
√l + √(l + 1) + … + √r ≦ (r – l + 1)√r [1, 10^6] の素数を試し割りで数えると, 10^9 回くらいの計算に 実際はもっと速いため KCS でもこれで OK

8 素数の個数を数える 効率的に数える方法として, エラトステネスの篩が有名 今回は, 複数の[l, r] のクエリに早く答える
詳しくは先輩たちに聞く or ググる 今回は, 複数の[l, r] のクエリに早く答える 方法を考えていこう.

9 高速化のアイディア 1 : 前計算 エラトステネスの篩を用いれば勝手に 前計算がされている. ・試し割りをしている人は, 配列を用意して
　前計算がされている. ・試し割りをしている人は, 配列を用意して p が素数だったら 配列の p 番目の 要素を 1 にしよう

10 高速化のアイディア2:累積和 刮目せよ！！！ さっき作った配列を… 1

11 高速化のアイディア2:累積和 刮目せよ！！！ さっき作った配列を… 1

12 高速化のアイディア2:累積和 刮目せよ！！！ さっき作った配列を… 右に足していく 1 1 2 3

13 高速化のアイディア2:累積和 この配列があると何が嬉しいか？ 考えてみよう！ 1 2 3