http://ourworld.compuserve.com/homepages/hlifchitz/Homepage.htm
エラトステネスの計算量は O(n*log(n)) らしいのですが、O(n^(1/2)*log(n))
で計算できるらしいです。dvi ファイルに詳しく書いてあります(僕は理解して
いませんが)。
>>694 との関連はよく分りませぬ。