哥德巴赫猜想9位数验证

哥德巴赫猜想

任一大于2的偶数都可写成两个质数之和

方案 1

#include<stdio.h>
#include<time.h>

typedef unsigned char Boolean;

#define TURE 1
#define FLASE 0
#define MAX_N 1000000000

Boolean isPrime(int n);

Boolean isPrime(int n){
	int i;

	for(i = 2;i < n && n%i;i++);

	return i >= n;
}

void main(void){
	int n;
	int i;
	int beginTime;
	int endTime;
	Boolean Goldbach;

	beginTime = clock();
	for(n = 6;n < MAX_N;n += 2){
		Goldbach = FLASE;
		
		for(i = 3;!Goldbach &&i < n/2;i += 2){
			if(isPrime(i) && isPrime(n - i)){
				printf("%d = %d + %d\n",n,i,n-i);
				Goldbach = TURE;
			}
		}
	}

	endTime = clock() - beginTime;
	printf("执行%d.%03d秒\n",endTime/1000,endTime%1000);
}

方案 2

#include<stdio.h>
#include<time.h>

typedef unsigned char Boolean;

#define TURE 1
#define FLASE 0
#define MAX_N 100000
#define PRIME 0
#define NOT_PRIME 1

Boolean isPrime(int n,Boolean *prime);
void filterPrime(Boolean *prime);

void filterPrime(Boolean *prime){
	int i;
	int j;

	for(i = 2*2;i < MAX_N;i += 2){
		prime[i] = NOT_PRIME;
	}
	i = 3;
	while(i*i < MAX_N){
		if(PRIME == prime[i]){
			for(j =i*i;j < MAX_N;j+=i){
				prime[j] = NOT_PRIME;
			}
		}
		i += 2;
	}
}
Boolean isPrime(int n,Boolean *prime){
	return prime[n] == PRIME;
}

void main(void){
	int n;
	int i;
	int beginTime;
	int endTime;
	Boolean Goldbach;
	Boolean prime[MAX_N] = {0};

	filterPrime(prime);
	beginTime = clock();
	for(n = 6;n < MAX_N;n += 2){
		Goldbach = FLASE;
		
		for(i = 3;!Goldbach &&i < n/2;i += 2){
			if(isPrime(i,prime) && isPrime(n - i,prime)){
				printf("%d = %d + %d\n",n,i,n-i);
				Goldbach = TURE;
			}
		}
	}

	endTime = clock() - beginTime;
	printf("执行%d.%03d秒\n",endTime/1000,endTime%1000);
}

方案 3（位运算）

#include<stdio.h>
#include<time.h>

typedef unsigned char Boolean;

#define TURE 1
#define FLASE 0
#define MAX_N 100000
#define PRIME 0
#define NOT_PRIME 1
#define INDEX(n) ((n) >> 3)
#define setBitNotPrime(n,i) n[INDEX(i)] |= (1 << (((i) & 0x07) ^ 0x07))

Boolean isPrime(int n,Boolean *prime);
void filterPrime(Boolean *prime);

void filterPrime(Boolean *prime){
	int i;
	int j;

	for(i = 2*2;i < MAX_N;i += 2){
		setBitNotPrime(prime,i);
	}
	i = 3;
	while(i*i < MAX_N){
		if(PRIME == prime[i]){
			for(j =i*i;j < MAX_N;j+=i){
				setBitNotPrime(prime,j);
			}
		}
		i += 2;
	}
}
Boolean isPrime(int n,Boolean *prime){
	return prime[n] == PRIME;
}

void main(void){
	int n;
	int i;
	int beginTime;
	int endTime;
	Boolean Goldbach;
	Boolean prime[MAX_N] = {0};

	filterPrime(prime);
	beginTime = clock();
	for(n = 6;n < MAX_N;n += 2){
		Goldbach = FLASE;
		
		for(i = 3;!Goldbach &&i < n/2;i += 2){
			if(isPrime(i,prime) && isPrime(n - i,prime)){
				printf("%d = %d + %d\n",n,i,n-i);
				Goldbach = TURE;
			}
		}
	}

	endTime = clock() - beginTime;
	printf("执行%d.%03d秒\n",endTime/1000,endTime%1000);
}