100 までの素数を列挙 in JavaScript2006年06月17日 16時33分

キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring」より。せっかくなので JavaScript 1.7 の新機能である Generator を使って書いてみる。

function countUp(n)
{
  n = n || 0;
  while (true)
    yield n++;
}

function filter(iterator, callback, thisObject)
{
  for (var i in iterator)
    if (callback.call(thisObject, i))
      yield i;
}

function takeWhile(iterator, callback, thisObject)
{
  var result = [];
  for (var i in iterator) {
    if (callback.call(thisObject, i))
      result.push(i);
    else
      break;
  }
  return result;
}

function prime()
{
  var primes = countUp(2);
  while (true) {
    let (n = primes.next()) {
      yield n;
      primes = filter(primes, function (i) { return i % n != 0; });
    }
  }
}

print(takeWhile(prime(), function (n) { return n < 100; }).join(" "));

だが、現時点では Generator が壊れている上、let 文 / let 式内で定義された関数の挙動がおかしいため、これはうまく動かない。そこで Generator を擬似的に実装、JavaScript 1.6 以下 / JScript でも動くように。

if (!this.StopIteration)
  this.StopIteration = { toString: function () { return "StopIteration"; } };

function countUp(n)
{
  n = n || 0;
  return { next: function () { return n++; } };
}

function filter(iterator, callback, thisObject)
{
  return {
    next: function () {
      while (true) {
        var i = iterator.next();
        if (callback.call(thisObject, i))
          return i;
      }
    }
  };
}

function takeWhile(iterator, callback, thisObject)
{
  var result = [];
  while (true) {
    try {
      var i = iterator.next();
      if (callback.call(thisObject, i))
        result.push(i);
      else
        break;
    } catch (e) {
      if (e == StopIteration)
        break;
      throw e;
    }
  }
  return result;
}

function prime()
{
  var primes = countUp(2);
  return {
    next: function () {
      var n = primes.next();
      primes = filter(primes, (function (n) {
        return function (i) { return i % n != 0; };
      })(n));
      return n;
    }
  };
}

print(takeWhile(prime(), function (n) { return n < 100; }).join(" "));
// 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

ある範囲から素数を抜き出すのではなく、ひたすら素数を生成し続けていくイメージ。速度は遅いけど。

ちなみに JScript 5.6 で試したら 949 番目の素数 7489 までは求められたが、それ以降は「実行時エラー: スタック領域が不足しています」となってしまった。