/*
    1,000以下の素数を求める
*/

#include <stdio.h>

int main(void)
{
    int  i, n;
    int  prime[500];                      /* 素数を格納する配列 */
    int  ptr = 0;                         /* 既に得られた素数の回数 */
    unsigned long  counter = 0;           /* 乗除の回数 */

    prime[ptr++] = 2;                     /* ２は素数である */
    prime[ptr++] = 3;                     /* ３も素数である */

    for (n = 5; n <= 1000; n += 2) {      /* 基数のみを対象とする */
        int  flag = 0;  　　　　　　　　　　/* (1) */          
        for (i = 1; counter++, prime[i] * prime[i] <= n; i++) {
            counter++;
            if (n % prime[i] == 0) {      /* 割り切れると素数ではない */
                flag = 1;                  /* (2) */       
                break;                    /* それ以上の繰返しは不要 */
            }
        }
        if (!flag)                        /* (3) */      
            prime[ptr++] = n;             /* 配列に登録 */
    }

    for (i = 0; i < ptr; i++)
        printf("%d\n", prime[i]);

    printf("乗除を行った回数 : %lu\n", counter);

    return (0);
}