アトキンの篩 - yarbの日記

素数を求めるアルゴリズムとして、エラトステネスの篩よりも計算量的には速いというアトキンの篩というのを実装してみようと思って検索したら、StakOverflowに Pythonの例があった。Wikipediaの記述のまんま。これをRubyに書き直してみた。

import math

def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results

def AtkinSieve(limit)
  primes = [2, 3, 5]
  sieve = [false] * (limit + 1)
  factor = Math.sqrt(limit).to_i + 1
  sqr_arr = (1..factor).map { |i| i**2 }

  sqr_arr.each_with_index do |i2, i|
    sqr_arr.each_with_index do |j2, j|
      n = 4*i2 + j2
      if (n <= limit) and (n % 12 == 1 or n % 12 == 5)
        sieve[n] = !sieve[n]
      end
      n = 3*i2 + j2
      if (n <= limit) and (n % 12 == 7)
        sieve[n] = !sieve[n]
      end
      if i > j
        n = 3*i2 - j2
        if (n <= limit) and (n % 12 == 11)
          sieve[n] = !sieve[n]
        end
      end
    end
  end

  (5..factor).each do |i|
    if sieve[i]
      (i**2..limit).step(i**2) do |j|
        sieve[j] = false
      end
    end
  end

  primes += (7..limit).find_all {|i| sieve[i]}

end

ダイレクトな翻訳じゃなくて、ちょっと計算の重複を省いたりRubyっぽさプラスしたりした。

で、思ったんだけど、こういうコードだとPythonのほうが読みやすい。Pythonだと、Rubyのendのようにブロックの閉じが不要なので全体が短いのがいい。縦に短いので全体のループのネスト構造が分かりやすい。コードハイライトした状態だとなおさらだけど、ループが全部 for になるので構造がクッキリと良く分かる。同様の理由で、rangeとイチイチ書くのって面倒だしダサいと思えるけど、コードを見るときにはハイライトされるので、よく分かる。RubyのEnumerableだと、いろんなメソッドがあるし、レシーバとしてもArrayとかRangeとかEnumeratorとか、まあ色々ありえる。each_charとかならレシーバは文字列だ。で、それらがリテラルだったりすると、そこがループになっていることがforよりも分かりづらい、ような気がする。今回はじめて知ったけど、Pythonでは range(start, end, step)という風に書ける。これはRubyなら、Range.new(start, end).step(step) と書く。ふつうRubyならリテラルに書いてしまうので、(0..100).step(2) となる。初めてこのRange#stepの記法を見た時には、すごいなRubyと思ったけど、Pythonのように馬鹿正直に range(s, e, s) とやるのもいいじゃん、と思ってしまった。Eloquentじゃないほうがいいこともあるよな、という。

配列へのappendも、Rubyだと、いろんなやり方があったりする。全体にPythonってそういう文脈依存や好みによるブレがない感じ。それはアルゴリズムの表現なんかには良いことに思える。とか思ってDjangoのソースを見ると、やたらとアンダースコアやらselfやらが一杯でてきてウゲっーとなったりもするんだけど。