# eratosthenes篩法 c語言

https://web.ntnu.edu.tw/~algo/Prime.html
#include <stdio.h> //4
#include <math.h>
#define N 100 //20000000
int sieve[N]={1,1}; // 1代表不是質數, 0代表是質數
void main() //eratosthenes
{
	// 只需要刪掉sqrt(N)以下的質數的倍數。
	for (int i=2; i<=sqrt(N); i++)
		if (!sieve[i])
			// k是倍率，j是質數i的倍數。當k-1,j同時-i
			// 當sieve[k]不是質數時，不用再次設定sieve[j]一次。
			// (k,j)=(5,15),(k,j)=(3,9)
			for (int k=N/i, j=i*k; k>=i; k--, j-=i){
				if (!sieve[k]){
					sieve[j] = 1;
				}
			}
	for (int i=2; i<=N; i++){
		if (!sieve[i])
			printf("%d ",i);
	}
}
// 運用小範圍的sieve[k]，避免存取大範圍的sieve[j]，
// 大幅減少cache miss。

# 使用 bitset 來取代 bool 陣列

#include <stdio.h> //5
#include <math.h>
#define N 100 //20000000
//一個 int 有 32 個位元，可以當作 32 個欄位來使用，節省記憶體空間，減少 cache miss 。
int sieve[(N>>5)+1]={1,1}; // 1代表不是質數, 0代表是質數

// inline關鍵字讓編譯器用「函式內容」覆蓋掉「函式呼叫」。
// https://www.greenend.org.uk/rjk/tech/inline.html
static inline int GET(int x) { return sieve[x>>5]>>(x&31) & 1; }
static inline void SET(int x) { sieve[x>>5] |= 1<<(x&31); }

void main() //eratosthenes篩法 c語言
{
	// printf("%d\n",sizeof(sieve)/sizeof(int));
	// register關鍵字讓變數存放於CPU register，加快存取速度。
	register int i, j, k;
	for (i=2; i<=sqrt(N); i++)
		if (!GET(i))
			for (k=N/i, j=i*k; k>=i; k--, j-=i)
				if (!GET(k))
					SET(j);
	for (int i=2; i<=N; i++){
		if (!GET(i))
			printf("%d ",i);
	}
}

# 不處理 2 的倍數

//令陣列第 0 格代表數字1 、陣列第 1 格代表數字3 、陣列第 2 格代表數字5 、 …… ，以此類推。
#include <stdio.h> //6
#include <math.h>
#define N 200 //1<<25,20000000
//const int N = 1<<7; //200; 1<<7 = 2^7
//一個 int 有 32 個位元，可以當作 32 個欄位來使用，節省記憶體空間，減少 cache miss 。
// 1代表不是質數, 0代表是質數
int sieve[(N>>6) + 1];	// 不處理2的倍數

#define GET(x) (sieve[x>>5]>>(x&31) & 1)
#define SET(x) (sieve[x>>5] |= 1<<(x&31))
#define N2I(i) ((i-1)>>1)	// 索引值 = (數字-1) / 2
#define I2N(i) ((i<<1)+1)	// 數字   = 索引值*2 + 1

// 驗證一個數字是不是質數
int isprime(int x){
	return x==2 || x>2 && (x&1) && !GET(N2I(x));
}

void main() //eratosthenes篩法 c語言
{
	int half_sqrt_N = sqrt(N) / 2;
	int half_N = N >> 1;
	register int i, j, k, ii;
	// 從3開始。N2I(3) = 1。
	for (i=1; i<=half_sqrt_N; i++)
		if (!GET(i))
			//					ii
			//for (j=2*i*(i+1), k=2*i+1; j<half_N; j+=k)
			//	SET(j);
			for (ii=I2N(i), j=N2I(N/ii), k=ii*j+i; j>=i; j--, k-=ii)
				if (!GET(j))
					SET(k);
	if (isprime(N))
		half_N += 1;
	printf("%d ",2);
	for (i=1; i<half_N; i++)
		if (!GET(i))
			printf("%d ",i*2+1);
}