【AtCoder版！蟻本】天下一プログラマーコンテスト2012 予選C A【エラトステネスの篩】

AtCoder版！蟻本のエラトステネスの篩の例題としてあげられている天下一プログラマーコンテスト2012 予選C をPythonで解いていきます。

リンク

A - 与えられた数より小さい素数の個数について

A - 与えられた数より小さい素数の個数について

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

制約

・自然数 n ( 1≤n≤10,000 ) が 1 行で与えられる。

解答例

# x以下の素数列挙
def sieve_of_eratosthenes(x):
    nums = [i for i in range(x+1)]

    root = int(pow(x,0.5))
    for i in range(2,root + 1):
        if nums[i] != 0:
            for j in range(i, x+1):
                if i*j >= x+1:
                    break
                nums[i*j] = 0

    primes = sorted(list(set(nums)))[2:]

    return primes

n = int(input())

ans = sieve_of_eratosthenes(n-1)

print(len(ans))

解説

与えられた整数Nより小さい素数の数を答える問題です。

ある値より小さい素数の数をかぞえるにはエラトステネスの篩という手法があります。

こちらのページで記載しましたので参照してください。
ebisuke33.hatenablog.com

この手法を用いることでansに素数の配列が代入されますので、その要素数を答えることでACをとることができました。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク