Day 151-Q4 | アトキンの篩（Sieve of Atkin）

問題

整数$N$が与えられる。以下のアトキンの篩の手続きに従って$N$以下の素数を全て求め、昇順に出力せよ。

手続き

サイズ$N+1$の真偽値配列is_primeを全てFalseで初期化。$N\ge2$ならis_prime[2]=True、$N\ge3$ならis_prime[3]=True。
$x^2\le N$、$y^2\le N$の全ての$(x,y)$の組について：$n=4x^2+y^2$が$N$以下かつ$n\bmod12\in\{1,5\}$なら反転／$n=3x^2+y^2$が$N$以下かつ$n\bmod12=7$なら反転／$x>y$のとき$n=3x^2-y^2$が$N$以下かつ$n\bmod12=11$なら反転。
$r^2\le N$の$r=5,6,\dots$について、is_prime[r]がTrueなら$r^2$の倍数すべてをFalseにする。
is_prime[i]=Trueの$i$を昇順出力。

入力形式

制約

$1 \le N \le 10^6$

入出力例

入力例1

出力例1

2 3 5 7 11 13 17 19 23 29

概念図：1〜30のトグル結果

ヒント（段階的開示）

ヒント1（方向性）

エラトステネスの篩は「素数の倍数を消す」引き算的発想だが、アトキンの篩は「特定の2次形式で表せる数を候補としてトグルする」足し算的・数論的発想。まずは手続きを疑わずそのまま実装し、小さい$N$で検算する。

ヒント2（アプローチ）

反転（トグル）がポイント。ある数$n$が複数の$(x,y)$の組で条件を満たすと複数回反転され、奇数回反転された数だけが最終的にTrueとして残る。

ヒント3（誘導）

def sieve_atkin(limit):
    is_prime = [False] * (limit + 1)
    if limit >= 2: is_prime[2] = True
    if limit >= 3: is_prime[3] = True
    x = 1
    while x * x <= limit:
        y = 1
        while y * y <= limit:
            n = 4*x*x + y*y
            if n <= limit and n % 12 in (1, 5):
                is_prime[n] = not is_prime[n]
            n = 3*x*x + y*y
            if n <= limit and n % 12 == 7:
                is_prime[n] = not is_prime[n]
            n = 3*x*x - y*y
            if x > y and n <= limit and n % 12 == 11:
                is_prime[n] = not is_prime[n]
            y += 1
        x += 1
    r = 5
    while r * r <= limit:
        if is_prime[r]:
            for i in range(r*r, limit+1, r*r):
                is_prime[i] = False
        r += 1
    return [i for i in range(limit+1) if is_prime[i]]

模範解答 (Python)

import sys

def sieve_atkin(limit):
    if limit < 2:
        return []
    is_prime = [False] * (limit + 1)
    if limit >= 2:
        is_prime[2] = True
    if limit >= 3:
        is_prime[3] = True
    x = 1
    while x * x <= limit:
        y = 1
        while y * y <= limit:
            n = 4 * x * x + y * y
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                is_prime[n] = not is_prime[n]
            n = 3 * x * x + y * y
            if n <= limit and n % 12 == 7:
                is_prime[n] = not is_prime[n]
            n = 3 * x * x - y * y
            if x > y and n <= limit and n % 12 == 11:
                is_prime[n] = not is_prime[n]
            y += 1
        x += 1
    r = 5
    while r * r <= limit:
        if is_prime[r]:
            for i in range(r * r, limit + 1, r * r):
                is_prime[i] = False
        r += 1
    return [i for i in range(limit + 1) if is_prime[i]]

def main():
    n = int(sys.stdin.read().split()[0])
    primes = sieve_atkin(n)
    print(" ".join(map(str, primes)))

main()

Step-by-Step 解説

1ベースケース
is_prime[2]=True, is_prime[3]=Trueを先に確定。

2$4x^2+y^2$（$n\bmod12\in\{1,5\}$）
$x{=}1,y{=}1{:}n{=}5$反転。$x{=}1,y{=}3{:}n{=}13$反転。$x{=}2,y{=}1{:}n{=}17$反転。$x{=}2,y{=}3{:}n{=}25$反転（後で除去対象）。$x{=}1,y{=}5{:}n{=}29$反転。

3$3x^2\pm y^2$の2式
$x{=}1,y{=}2{:}n{=}7$反転。$x{=}2,y{=}1(x{>}y){:}n{=}11$反転。$x{=}3,y{=}2(x{>}y){:}n{=}23$反転。こうして5〜29の候補が奇数回の反転を経てTrueになる。

4平方因子の除去
is_prime[25]=Trueだが$r{=}5$でis_prime[5]=Trueなので$25{=}5^2$がFalseに戻る。最終的にTrueは2 3 5 7 11 13 17 19 23 29で既知の素数と完全一致。

よくあるミス

ミス	原因	正しい書き方
反転を「代入」だと誤解	トグルの意味を取り違える	必ず`not is_prime[n]`による反転
$x>y$を全式に付け忘れる	3式を同じ扱いにする	3番目の式（$3x^2-y^2$）だけ$x>y$が必須
平方因子除去ステップを忘れる	ステップ3で終わりと誤解	$r^2$の倍数を篩い落とすステップ4を必ず実行
$r$を2から開始	篩全体を一様に扱おうとする	2,3はベースケース済みなので$r=5$から開始
3つの$\bmod12$条件を1つにまとめる	式ごとの対応を混同	$\{1,5\},\{7\},\{11\}$は各式に独立して対応

次のステップ

発展: $N=10^6$で実測し、単純なエラトステネスの篩と実行時間を比較する。
次回予告: Radonの定理の構成的証明（Radon Partition）

自己評価

完全理解おおむね理解要復習

Day 151-Q4 — アトキンの篩（Sieve of Atkin）

問題

手続き