您好,登錄后才能下訂單哦!
1、問(wèn)題描述
大于等于6以上的偶數(shù)總有 = 2個(gè)質(zhì)數(shù)之和;
例:12 = 3 + 9 X
12 = 5 + 7 V (哥德巴赫猜想成立);
基本分析
2、基礎(chǔ)算法代碼實(shí)現(xiàn)
#include<stdio.h> 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開(kāi)始---userNumber的所有數(shù)字進(jìn)行哥德巴赫猜想 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 && n%i; i++) ; return i >= n; } void main(void){ int num; printf("請(qǐng)輸入一個(gè)邊界數(shù): "); scanf("%d", &num); if(FALSE == Gguess(num)){ printf("哥德巴赫猜想失敗\n"); }else{ printf("哥德巴赫猜想成功了\n"); } }
結(jié)果截圖
算法分析:
基礎(chǔ)算法,的真正耗時(shí)的主要運(yùn)算在"質(zhì)數(shù)判斷"上,無(wú)需計(jì)算,算法速度將大大加快。
3、中級(jí)算法
(1)、思路:先把9位以?xún)?nèi)的所有質(zhì)數(shù)都找出來(lái),是質(zhì)數(shù)的為0,不是質(zhì)數(shù)的為1,判斷是否為質(zhì)數(shù)查表即可;
篩選法:以數(shù)組下標(biāo)為數(shù)值本身,而相關(guān)元素的值為0或1,0:是質(zhì)數(shù),1:非質(zhì)數(shù);
算法模型:
(2)、判斷是否為質(zhì)數(shù)的高效代碼
#include<stdio.h> #include<math.h> #include<malloc.h> 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判斷到根號(hào)number的長(zhǎng)度即可 if(pool[i] == 0){ for(j = i*i; j < number; j += i){ //前面的都重復(fù)的判斷過(guò)了 pool[j] = 1; //非質(zhì)數(shù)標(biāo)記為1 } } } *p = pool; } void main(void){ int number; char *p = NULL; int i; printf("請(qǐng)輸入多少位內(nèi)的質(zhì)數(shù): "); scanf("%d", &number); findPrime(number, &p); for(i = 3; i < number; i++){ if(p[i] == 0){ printf("%d ", i); } } printf("\n"); free(p); }
(3)、結(jié)果截圖
算法分析:
因?yàn)橛玫妮o助空間是char類(lèi)型的,而只需存儲(chǔ)0/1,所有太浪費(fèi)內(nèi)存空間,并且都是* 、/這類(lèi),運(yùn)算速度比較慢
4、極端算法
(1)、位運(yùn)算的判斷質(zhì)數(shù)
#include<stdio.h> #include<math.h> #include<malloc.h> //位運(yùn)算計(jì)算的效率更快 #define SET_BIT(byte, i) (byte |= 1 << (7 ^ (i))) //設(shè)置這個(gè)字節(jié)的指定位為1 #define CLR_BIT(byte, i) (byte &= ~(1 << (7 ^ (i)))) //設(shè)置這個(gè)字節(jié)的指定位為0 #define GET_BIT(byte, i) !!((byte) & (1 << (7^(i)))) //得到這個(gè)字節(jié)的指定位 // num >> 3 數(shù)組下標(biāo) // 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判斷到根號(hào)number的長(zhǎng)度即可 if(GET_BIT(pool[i >> 3], i & 7) == 0){ for(j = i*i; j < number; j += i){ //前面的都重復(fù)的判斷過(guò)了 SET_BIT(pool[j >> 3], j & 7);//非質(zhì)數(shù)標(biāo)記為1 } } } *p = pool; } void main(void){ int number; char *p = NULL; int i; printf("請(qǐng)輸入多少位內(nèi)的質(zhì)數(shù): "); 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<stdio.h> #include<math.h> #include<malloc.h> typedef unsigned char boolean; #define TRUE 1 #define FALSE 0 //位運(yùn)算計(jì)算的效率更快 #define SET_BIT(byte, i) (byte |= 1 << (7 ^ (i))) //設(shè)置這個(gè)字節(jié)的指定位為1 #define CLR_BIT(byte, i) (byte &= ~(1 << (7 ^ (i)))) //設(shè)置這個(gè)字節(jié)的指定位為0 #define GET_BIT(byte, i) !!((byte) & (1 << (7^(i)))) //得到這個(gè)字節(jié)的指定位 // num >> 3 數(shù)組下標(biāo) // 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開(kāi)始---userNumber的所有數(shù)字進(jìn)行哥德巴赫猜想 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:表示為質(zhì)數(shù); } 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判斷到根號(hào)number的長(zhǎng)度即可 if(GET_BIT(pool[i >> 3], i & 7) == 0){ for(j = i*i; j < number; j += i){ //前面的都重復(fù)的判斷過(guò)了 SET_BIT(pool[j >> 3], j & 7);//非質(zhì)數(shù)標(biāo)記為1 } } } *p = pool; } void main(void){ int num; char *p; printf("請(qǐng)輸入一個(gè)邊界數(shù): "); scanf("%d", &num); findPrime(num, &p); if(FALSE == Gguess(num, p)){ printf("哥德巴赫猜想失敗\n"); }else{ printf("哥德巴赫猜想成功了\n"); } }
結(jié)果截圖:
算法分析:
關(guān)鍵在質(zhì)數(shù)判斷上面進(jìn)行的算法的極簡(jiǎn)優(yōu)化,由char-->位的簡(jiǎn)化,和位運(yùn)算的執(zhí)行速率極高;
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。