1、问题描述
创新互联服务项目包括波密网站建设、波密网站制作、波密网页制作以及波密网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，波密网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到波密省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
大于等于6以上的偶数总有 = 2个质数之和；
例：12 = 3 + 9 X
12 = 5 + 7 V (哥德巴赫猜想成立)；
基本分析
2、基础算法代码实现
#include
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
boolean isPrime(int n);
boolean Gguess(int userNumber);
boolean Gguess(int userNumber){
int num;
int i;
int flag = TRUE;
for(num = 6; TRUE == flag && num < userNumber; num += 2){ //从6开始---userNumber的所有数字进行哥德巴赫猜想
flag = FALSE;
for(i = 3; i < num && FALSE == flag; i += 2){
if(isPrime(i) && isPrime(num-i)){
flag = TRUE;
printf("%d = %d + %d\n", num, i, num-i);
}
}
}
}
boolean isPrime(int n){
int i;
for(i = 2; i= n;
}
void main(void){
int num;
printf("请输入一个边界数: ");
scanf("%d", &num);
if(FALSE == Gguess(num)){
printf("哥德巴赫猜想失败\n");
}else{
printf("哥德巴赫猜想成功了\n");
}
}
结果截图
算法分析：
基础算法，的真正耗时的主要运算在"质数判断"上，无需计算，算法速度将大大加快。
3、中级算法
(1)、思路：先把9位以内的所有质数都找出来，是质数的为0，不是质数的为1，判断是否为质数查表即可；
筛选法：以数组下标为数值本身，而相关元素的值为0或1，0：是质数，1：非质数；
算法模型：
(2)、判断是否为质数的高效代码
#include
#include
#include
void findPrime(int number, char **p);
void findPrime(int number, char **p){
int len = (int)(sqrt(number));
int i;
int j;
char *pool;
pool = (char *)calloc(sizeof(char), number);
for(i = 2; i < len; i++){ //从2判断到根号number的长度即可
if(pool[i] == 0){
for(j = i*i; j < number; j += i){ //前面的都重复的判断过了
pool[j] = 1; //非质数标记为1
}
}
}
*p = pool;
}
void main(void){
int number;
char *p = NULL;
int i;
printf("请输入多少位内的质数: ");
scanf("%d", &number);
findPrime(number, &p);
for(i = 3; i < number; i++){
if(p[i] == 0){
printf("%d ", i);
}
}
printf("\n");
free(p);
}
(3)、结果截图
算法分析：
因为用的辅助空间是char类型的，而只需存储0/1，所有太浪费内存空间，并且都是* 、/这类，运算速度比较慢
4、极端算法
(1)、位运算的判断质数
#include
#include
#include
//位运算计算的效率更快
#define SET_BIT(byte, i) (byte |= 1 << (7 ^ (i))) //设置这个字节的指定位为1
#define CLR_BIT(byte, i) (byte &= ~(1 << (7 ^ (i)))) //设置这个字节的指定位为0
#define GET_BIT(byte, i) !!((byte) & (1 << (7^(i)))) //得到这个字节的指定位
// num >> 3 数组下标
// num & 7 <===> num % 8
void findPrime(int number, char **p);
void findPrime(int number, char **p){
int len = (int)(sqrt(number));
int i;
int j;
char *pool;
pool = (char *)calloc(sizeof(char), (number+7)>>3);
for(i = 2; i < len; i++){ //从2判断到根号number的长度即可
if(GET_BIT(pool[i >> 3], i & 7) == 0){
for(j = i*i; j < number; j += i){ //前面的都重复的判断过了
SET_BIT(pool[j >> 3], j & 7);//非质数标记为1
}
}
}
*p = pool;
}
void main(void){
int number;
char *p = NULL;
int i;
printf("请输入多少位内的质数: ");
scanf("%d", &number);
findPrime(number, &p);
for(i = 3; i < number; i++){
if(GET_BIT(p[i >> 3], i & 7) == 0){
printf("%d ", i);
}
}
printf("\n");
free(p);
}
(2)、哥德巴赫猜想的完整算法
#include
#include
#include
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
//位运算计算的效率更快
#define SET_BIT(byte, i) (byte |= 1 << (7 ^ (i))) //设置这个字节的指定位为1
#define CLR_BIT(byte, i) (byte &= ~(1 << (7 ^ (i)))) //设置这个字节的指定位为0
#define GET_BIT(byte, i) !!((byte) & (1 << (7^(i)))) //得到这个字节的指定位
// num >> 3 数组下标
// num & 7 <===> num % 8
void findPrime(int number, char **p);
boolean isPrime(int num, char *p);
boolean Gguess(int userNumber, char *p);
boolean Gguess(int userNumber, char *p){
int num;
int i;
int flag = TRUE;
for(num = 6; TRUE == flag && num < userNumber; num += 2){ //从6开始---userNumber的所有数字进行哥德巴赫猜想
flag = FALSE;
for(i = 3; i < num && FALSE == flag; i += 2){
if(isPrime(i, p) && isPrime(num-i, p)){
flag = TRUE;
printf("%d = %d + %d\n", num, i, num-i);
}
}
}
return flag;
}
boolean isPrime(int num, char *p){
return GET_BIT(p[num >> 3], num & 7) == 0; //0：表示为质数;
}
void findPrime(int number, char **p){
int len = (int)(sqrt(number));
int i;
int j;
char *pool;
pool = (char *)calloc(sizeof(char), (number+7)>>3);
for(i = 2; i < len; i++){ //从2判断到根号number的长度即可
if(GET_BIT(pool[i >> 3], i & 7) == 0){
for(j = i*i; j < number; j += i){ //前面的都重复的判断过了
SET_BIT(pool[j >> 3], j & 7);//非质数标记为1
}
}
}
*p = pool;
}
void main(void){
int num;
char *p;
printf("请输入一个边界数: ");
scanf("%d", &num);
findPrime(num, &p);
if(FALSE == Gguess(num, p)){
printf("哥德巴赫猜想失败\n");
}else{
printf("哥德巴赫猜想成功了\n");
}
}
结果截图：
算法分析：
关键在质数判断上面进行的算法的极简优化，由char-->位的简化，和位运算的执行速率极高；
文章题目：哥德巴赫猜想验证
分享网址：
http://cdkjz.cn/article/iieics.html
