素数を表示する（エラトステネスのふるい）

prime.c

#include <stdio.h>
#include <math.h>   // sqrt用
#include <time.h>   // clock用

#define NUM 10000
int main(void){
    clock_t start, end;
    int i, j;
    int prime[NUM];
    
    start = clock();
    
    // 配列の初期化
    for (i = 0; i < NUM; i++)
    {
        prime[i] = 1;
    }
    
    // エラトステネスのふるいの実装
    // NUMの平方根より小さい素数の倍数を消せば、残りは素数
    for (i = 2; i < sqrt(NUM); i++)
    {
        // 素数の倍数の判定
        if(prime[i])
        {
            // 素数の倍数を消す
            for (j = i; i * j < NUM; j++)
            {
                prime[i * j] = 0;
            }
        }
    }
    
    for (i = 2; i < NUM; i++)
    {
        if(prime[i]) printf("%6d", i);
    }
    
    end = clock();
    
    printf("\n\n%d[ms]", end - start);
    
    return 0;
}