prime_number.c

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

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

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


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


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

/* メイン関数 */
int main()
{
	//フラグ配列初期化
	memset(flagNote, 0xFF, sizeof(flagNote));

	//ふるい
	calc();
	
	//コンソール出力
	out2console();

	return 0;
}

/* ふるい */
void calc()
{
	//ループ用変数
	ULONG n;  //ノートを進行する変数
	ULONG m;  //倍数を進行する変数
	ULONG pos; //ノートポジション（ビット単位）
	
	/* ふるい */
	n = 3;
	while((n * n) <= MAX) { //ノート進行
		//この数は素数である
		/* 倍数消しループ */
		
		#pragma omp parallel for
		for(m = n; m <= (MAX / n); m += 2) //素数の倍数は素数ではない
			clearFlag(((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	");
	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("	");
		}
	}
	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));
}