Photo by formulanone 青木です。paizaラーニング担当のエンジニアです。 人間、どうしても素数を数えて落ち着きたいときってあると思います。 順に数えてくと、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31……自分で数えるのは限界がありますよね。 そんなときはプログラムに数えてもらいましょう。 今回は、素数を数えるためのいろいろなアルゴリズムや高速化について書きます。(言語はJavaを使います) プログラミング初心者の方、アルゴリズムについて勉強したい方、素数が大好きな皆さんの参考になればと思います。 素数とは孤独な数字 素数とは、1と自分自身の数以外の自然数では割り切れない孤独な数字です。(ってプッチ神父が言ってました) たとえば、7は1と7以外の自然数では割り切れないので素数です。8は2や4で割り切れるので素数ではありません。 ※1は諸説