/*
    http://t...content-available-to-author-only...h.net/test/read.cgi/tech/1354070278/657
    657 名前：デフォルトの名無しさん [sage]： 2012/12/29(土) 23:46:55.91
        [1] 授業単元：課題2
        [2] 問題文(含コード&リンク)：
        素数を小さいものから順に，改行区切りで表示するプログラムを作成せよ．
        なお，50万個程度出力すれば充分とする．
        [3] 環境
          [3.1] OS：windows
          [3.2] コンパイラ名とバージョン： gcc
          [3.3] 言語：C
        [4] 期限： ([2013年1月4日まで]
        [5] その他の制限：標準ライブラリのみ使用可

        できればコメントも付けてくださいよろしくお願いします
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NN  (500000)            // 求める個数

int main()
{
    int *data;                  // 素数入れ先
    int count;                  // 個数カウンタ
    int i, j;

    // 素数入れ先確保
    if (NULL == (data = malloc(sizeof(int) * NN))) {
        fprintf(stderr, "メモリ確保失敗\n");
        exit(1);
    }
    
    // 素数計算
    data[0] = 2;
    count = 1;
    for (i = 3;; i += 2) {                  // 3以上の奇数のみ計算する
        for (j = 0; j < count; j++) {
            if (data[j] * data[j] > i) {    // 割る数の2乗が割られる数を越える計算は必要ない
                data[count++] = i;          // ここまでで割り切られることが無かったので追加
                break;
            }
            if (i % data[j] == 0) {         // これまでに求められた素数で割りきれるか
                break;
            }
        }
        if (count >= NN) {                  // 指定個数に達したので終了
            break;
        }
    }

    // 出力
    for (i = 0; i < NN; i++) {
        printf("%d\n", data[i]);
    }

    // 素数入れ先解放
    free(data);

    // 終了
    return 0;
}