エラトステネスの篩を改良したサンダラムの篩によって素数を効率よく求めることができました。
さらなる改良は可能か
サンダラムの篩をさらに改良することはできるでしょうか？
原理としては可能です。
どのように改良すればよいのか、それはサンダラムのふるいがどのように改良されたのかをよく分析するとわかります。
話は少しそれますが、原理を無視して、結論の式、i+j+ijの式だけみて求めようとすると、早とちりして失敗するかもしれませんよ。消し込む(ふるいにかける)数が増えたりして。
本当に効率がよくなっているか、実際にプログラミングして検証するのが一番説得力あるのですが、それはまた別の機会にするとして、ここでは改良の方法について考えます。
改良点
改良点は両者を比較するとわかります。
エラトステネスの篩
(1)ふるいに自然数をのせる。
(2)そこから合成数を振り落とす。
サンダラムの篩
(1)ふるいに奇数をのせる。
(2)そこから合成数を振り落とす。
大きな違いは、最初にふるいにのせる数です。
のせる数をかえたことで、合成数かどうかを判定する方法も変わってきます。合成数の判定を失敗すると、返って効率が悪くなる可能性もあるというのが、さきほどの脱線した話です。
したがって、さらに改良するには、ふるいにのせる数をさらに少なくすることが鍵となります。
サンダラムは、偶数を最初からはずしていました。ですからこんどは、3の倍数を最初からはずしておくのです。これで、奇数の三分の一が消えますから、ふるいに残るのは奇数の3分の2となります。
合成数の判定処理が増えてしまうので単純に計算できないところもありますが、大雑把にみて、エラトステネスの篩にくらべると三倍の効率化が期待されます。
もっと効率があげられるか
サンダラムの改良は言い換えると、2と3を既知の素数として処理することです。
したがって、2,3,5を既知の素数として考えればさらなる効率化が期待されます。
繰り返しになりますが、既知の素数を増やせば増やすほど合成数の振り落し処理が増えていきますので、つまり今度はプログラムの規模が大きくなっていくという問題をかかえます。
EXCELのVBAでも簡単にプログラミングできるので、機会があれば効率を評価してみたいです。
まとめ
既知の素数を増やすことでサンダラムの篩は改良が可能。
[ad#foot]
