以前に皆さま方からアドバイスをいただいて
『足し算のみで素数列を生成するジェネリックなイテレータの実装』
を当時O(N^3)という酷さでしたが、このたびほぼ O(N) の新たなアルゴリズムと実装が出来ましたのでご報告します

足し算の総回数を O(N log log N) すなわちほぼ O(N) 近くにすることに成功しました
具体的には 1億(＝10^8) までの素数生成に必要とする 足し算の総回数が 2.5億回 とリニアになりました
前回と異なりメモ化をしていますがこちらも工夫により配列の長さを O(√N / log N) に抑えることに成功しました
具体的には 1億(＝10^8) までの素数生成に必要とする 配列の長さが 1231 と非常に小さな領域のみで実現できました

10^kまでの素数を順に生成時の足し算の総回数 O(N log log N)
10^1　4.70×10^1＝47
10^2　2.03×10^2＝203
10^3　1.90×10^3＝1903
10^4　1.95×10^4＝19508
10^5　2.12×10^5＝212715
10^6　2.27×10^6＝2278220
10^7　2.41×10^7＝24148110
10^8　2.54×10^8＝254082528

10^kまでの素数を順に生成時の配列の長さ O(√N / log N)
10^1　4
10^2　6
10^3　13
10^4　27
10^5　67
10^6　170
10^7　448
10^8　1231

メモリ使用もこの程度の少なさで
足し算を2.5億回とその比較だけで1億までの全ての素数を順に出力できるようになりました
このスレは数学が得意な方々が多いようなのでご検証よろしくお願いします