Python3で解く AtCoder Beginner Contest 149 C - Next Prime

自分自身以上の素数を求める問題。テストサンプルに制約の中で最大の素数のヒントがあるので、そこまでのテーブルがあればいい。 あとは二分探索で探す。bisect_left, bisect_rightどちらでもできるが、たまに混乱するので、どういう風に考えて使うか軽くまとめた。

目次

概要

問題
1. 以上の素数のうち、最小のものは？

制約

• 

---

解くときに考えた内容

• よりも一つ大きい素数を求める方法はよくわからん。
• その場合、どうやるか。

• 制約の範囲内 + 範囲外の最小の素数のテーブルを持つ

  素数テーブルの求め方
  エラトステネスの篩

  1. 2から（今回は100003）までの探索リストを作成する。
     (テストサンプルに100000を超える最小の素数の答えがある。)
  2. 探索する先頭の数を素数リストに移動する。
  3. その定数倍の値を探索リストからふるい落す。
  4. 振い落としの素数リストへの移動と探索リストのふるい落としのステップを素数リストに移動する値がxの平方根まで行う。
  5. 探索リストに残った数を素数リストに移動する。
  6. 出来上がったのが素数テーブル

• その後に、をテーブル内で二分探索する。

  二分探索
  1. bisect_left(P, x)とすればになるような個数が返ってくる。その個数とは求めたいindexであるのでが求めるもの。

参考

P = [2, 3, 5, 7, 11, 13, 17 ,19 ,23]
x = 19
bisect_left(P, 19) というのはリスト内の19未満の要素の個数 = 7
これは19以上で最も小さい素数のindexでもある。
bisect_right(P, 19)というのはリスト内の19以下の要素の個数=8
なので、今回bisect_rightを使う場合は、素数であるかどうかで分けてからならそれでもいい。

---

コード

bisect_left

from bisect import bisect_left

def eratosthenes(n):
    A = [i for i in range(2, n+1)]
    P = []
    i = 2
    while i**2 <= n:
        prime = min(A)
        P.append(prime)
        j = 0
        while j < len(A):
            if A[j] % prime == 0:
                A.pop(j)
                continue
            j += 1
        i += 1    
    for a in A:
        P.append(a)
    return P
    
x = int(input())
prime_table = eratosthenes(100003)
idx = bisect_left(prime_table, x)
ans = prime_table[idx]
print(ans)

bisect_right

from bisect import bisect_right

def eratosthenes(n):
    A = [i for i in range(2, n+1)]
    P = []
    i = 2
    while i**2 <= n:
        prime = min(A)
        P.append(prime)
        j = 0
        while j < len(A):
            if A[j] % prime == 0:
                A.pop(j)
                continue
            j += 1
        i += 1    
    for a in A:
        P.append(a)
    return P
    
x = int(input())
prime_table = eratosthenes(100003)
prime_set = set(prime_table)
if x in prime_set:
    print(x)
else:
    idx = bisect_right(prime_table, x)
    ans = prime_table[idx]
    print(ans)

---

書籍

アルゴリズムの参考書籍

まだ、発売されていないが内容に期待している一冊。

• 問題解決力を鍛える!アルゴリズムとデータ構造
  けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
  投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

drken1215.hatenablog.com

• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

最近ポチった書籍

• ゼロからつくるPython機械学習プログラミング入門

機械学習スタートアップシリーズ ゼロからつくるPython機械学習プログラミング入門 (KS情報科学専門書)

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク・強化学習・教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。これは別記事で紹介する予定である。

• 実用的でないPythonプログラミング

実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!

バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。

blacktanktop.hatenablog.com

---