prime_number.c

#include <stdio.h>
#include <string.h>

/***********************************************************/
/*** 定数 ****/
/* 求める素数の範囲の最大値 */
#define MAX 4000000000L
/* 出力の横の長さ */
#define SPLIT_X 10
/***********************************************************/

/* 省略型 */
typedef unsigned long long   ULONG;
typedef unsigned char     BYTE;

//フラグビット配列(MAX / 2 / 8)
BYTE flagNote[MAX / 16];

/* プロトタイプ */
void calc();
void out2console();
BYTE getFlag(ULONG);
void setFlag(ULONG);
void clearFlag(ULONG);

/* メイン関数 */
int main()
{
  //フラグ配列初期化
  memset(flagNote, 0x00, sizeof(flagNote));
  //ふるい
  calc();
  //コンソール出力
  out2console();

  return 0;
}

/* ふるい */
void calc()
{
  //ループ用変数
  ULONG n;  //ノートを進行する変数
  ULONG m;  //倍数を進行する変数
  
  /* ふるい */
  n = 3;
  while(n * n <= MAX) { //ノート進行
    //この数は素数である
    /* 倍数消しループ */
    
    #pragma omp parallel for //OpenMPによる並列演算
    for(m = n; m <= MAX / n; m += 2) //素数の倍数は素数ではない
      setFlag(n * m / 2 - 1); //フラグを消す
    
    n += 2;
    while(getFlag(n / 2 - 1)) n += 2; //次へ進行
  }
  /* ふるい・終わり */
}

/* コンソール出力 */
void out2console()
{
  int split = 0; //横カウント
  ULONG i; //ループ用
  ULONG pos;

  //2は例外として・・・
  printf("2\t");
  split++;

  for(i = 3; i <= MAX; i += 2) {
    if(!getFlag((i / 2) - 1)) { //フラグがあるか
      split++;
      
      printf("%lld", i); //出力
      
      if(split == SPLIT_X) {
        printf("\n");
        split = 0;
      }
      else printf("\t");
    }
  }
  printf("\n"); //整形用
}


/****** ビットフラグ操作 ******/
/* フラグ取得 */
BYTE getFlag(ULONG pos) {
  return ((flagNote[pos / 8] >> (pos % 8)) & 0x01);
}

/* フラグ立て */
void setFlag(ULONG pos) {
  flagNote[pos / 8] |= (0x01 << (pos % 8));
}

/* フラグ消し */
void clearFlag(ULONG pos) {
  flagNote[pos / 8] &= ~(0x01 << (pos % 8));
}