読者です 読者をやめる 読者になる 読者になる

at kaneshin

Free space for me.

高速な素数判定

Project Eulerに素数を判定させる問題があったので、その解答の一例

基本はエラトステネスの篩の原理と同じだが、篩は0x00と0xFF (0 or 1でも)で管理してあり、篩の中で0となっている要素数が低いものが次の素数となっています。

その素数を基に、0でない値 (0xFFなど) を素数倍のとこにフィリングしていきます。