C Programming

「エラトステネスのふるい」のサンプル

#include <stdio.h>
#define NUM 1000

void main()
{
　int prime[ NUM ], i, j;

　for ( i = 2; i < NUM; i++ )
　　prime[ i ] = 1; // 1を立てておく

　for ( i = 2; i < NUM; i++ ) {
　　if ( prime[ i ] == 1 ) { // 1ならそれは最初にみつかった素数
　　　for ( j = 2; i * j < NUM; j++ )
　　　　prime[ i * j ] = 0; // i以外のiの倍数を全て倒す
　　}
　}

　printf( "素数：1 " );
　for ( i = 2; i < NUM; i++ ) {
　　if ( prime[ i ] == 1 )
　　　printf( "%d ", i );
　}
}

結果は出力してのお楽しみだ。