>>239
素数かどうかを調べるのは>>236が書いているように足し算だけで可能です
必要となる足し算の数は>>241が書いているようにO(N log log N)です
足し算平均2.5回は1億まで素数を列挙した時の話であって>>240が書いているようにNに対してわずかですが増えていきます