エラトステネスの篩

パッケージJava製品開発担当の大です。こんにちは。
震災から11日が経ちました。被害に合われた方々は、現在も大変なご苦労をされていることと思います。
謹んでお見舞い申し上げます。

さて、前回、前々回と素数にまつわる話を書きました。
その際Wikipediaをウロウロしてたらエラトステネスの篩のページにあたったのですが、
アルゴリズムを可視化しているアニメーションGIFが貼ってあって、わかりやすくていいなぁと思ったので、自分でも書いてみたくなりました。で、お手軽にJavaScriptで書いてみました。

可視化の前に

エラトステネスの篩（ふるい）についてものすごくさらっと説明しておくと、ある整数以下の全ての素数を発見するためのアルゴリズムです。
詳しいことはWikipediaのページを見てください。

JavaScriptで可視化

実行ボタンを押してみてください。可視化します。
2～2000までの値を指定して実行できます。

ソース

こんな感じです。久しぶりにJavaScriptを書いてみましたが、やっぱりクロージャのある言語は楽しいですね！
jQueryは全然使いこなせてないですが。。。

function Eratosthenes($) {
  var UNKNOWN = -1;
  var DEFAULT_LENGTH = 100;
  var MIN_LENGTH = 2;
  var MAX_LENGTH = 2000;
  var self = this;
  var list;
  var queue;

  // 数列を篩にかけます。
  // 素数か合成数かが判別できた時点でqueueに入れてます。
  this.sieve = function() {
    for (var i = 2; i < list.length; i++) {
      if (list[i] != UNKNOWN) {
        continue;
      }
      var color = newColor();
      list[i] = i;
      queue[queue.length] = {n: i, color: color};

      if (i * i > list.length) {
        continue;
      }

      for (var j = i * 2; j < list.length; j += i) {
        if (list[j] != UNKNOWN) {
          continue;
        }
        list[j] = i;
        queue[queue.length] = {n: j, color: color};
      }
    }
    this.visualize(0);
  }

  // queueの順に判別した様を可視化します。
  this.visualize = function(index) {
    if (index < queue.length) {
      var n = queue[index].n;
      if (n == list[n]) {
        $('#primes').append(' ' + n);
        $('#td' + n).css('border-color', '#ff0000');
      }
      $('#td' + n).css('background-color', queue[index].color);
      setTimeout(function () {self.visualize(index + 1);}, Math.floor(10000/list.length));
    }
  }

  // 色を適当に作成します。
  // 薄めの色で隣り合う色がなるべく判別しやすいように。。。
  var newColor = (function() {
    var times = 0;
    return function() {
      var color = '#';
      for (var i = 0; i < 3; i++) {
        var c = times % 3 == i ? 0xFF : (Math.floor(Math.random() * 0x7F) + 0x7F);
        color += c.toString(16);
      }
      times++;
      return color;
    };
  })();

  // 初期化します。
  var init = function() {
    var len = parseInt($('#length').val());
    if (isNaN(len)) {
      len = DEFAULT_LENGTH;
    } else {
      len = Math.max(len, MIN_LENGTH);
      len = Math.min(len, MAX_LENGTH);
    }
    $('#length').val(len);
    list = new Array(len + 1);
    list[0] = 0;
    list[1] = 1;
    for (var i = 2; i < list.length; i++) {
      list[i] = UNKNOWN;
    }
    $('#nlist').empty();
    var tr;
    for (var i = 1; i < list.length; i++) {
      if (i % 10 == 1) {
        tr = $('<tr>');
        $('#nlist').append(tr);
      }
      tr.append($('<td>').attr('id', 'td' + i).text(i));
    }
    $('#primes').empty();
    queue = new Array();
  }
  
  init();
}