動いて楽しいアルゴリズム！　第２回〜素数の判定とエラトステネスのふるい
日経ソフトウェア　第141号　2009.8.1

この記事の情報
掲載誌	日経ソフトウェア　第141号（2009.8.1）
ページ数	4ページ　（全3930字）
形式	PDFファイル形式　（267kb）
雑誌掲載位置	96〜99ページ目

第２回　今回のテーマは素数の判定です。素数とは他の整数で割り切れない正の整数のことです。１は素数ではない約束なので，２，３，５，７，１１などが素数です。　整数ｎが素数かどうかを判定するには，ｎより小さい様々な数で割ってみるという“力任せのアルゴリズム”しかありません。ただし，アルゴリズムを工夫するアイディアがいくつかあります。２〜ｎ−１までのすべての整数で割ってみる　リスト１は，キー入力された整数…