Microsoft Word - ACL chapter02-5ed.docx

Transcription

1 第 2 章神奇的質數 什麼是質數 1 1 1

2 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 以內的質數有 25 個

3 第 2 章神奇的質數 100~200 之間的質數有 21 個 200~300 之間的質數有 16 個 300~400 之間的質數有 16 個 400~500 之間的質數有 17 個 500~600 之間的質數有 14 個 600~700 之間的質數有 16 個 700~800 之間的質數有 14 個 800~900 之間的質數有 15 個 900~1000 之間的質數有 14 個 GIMPS 驗證質數 1000 質數驗證演算法 確定性演算法 隨機演算法

4 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 N 2 N-1 N N-1 int is_prime(int n) int i; if(n <= 1) //1 n<=1 0 for(i = 2; i < n; i++) if(n % i == 0) // n i return 1; N N N-1 n N= N 3 5 N 5 is_prime() int is_prime(int n) int i; if(n <= 1) //1 n<=

5 第 2 章神奇的質數 for(i = 2; i * i <= n; i++) if(n % i == 0) i return 1; for i 2 n 尋找質數的演算法 1000 is_prime() 1000 #include <stdio.h> #include<conio.h> int is_prime(int n) int i; if(n <= 1) //1 n<=1 0 for(i = 2; i * i <= n; i++) if(n % i == 0) i return 1; int main() int i,n=0,t=1;

6 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 printf("1000 \n"); for(i=2;i<1000;i++) if(is_prime(i)) n++; t++; printf("%4d",i); if(t>10) printf("\n"); t=1; printf("\n1000 %d \n",n); // 10 getch(); 1000 is_prime() is_prime()

7 第 2 章神奇的質數 Eratosthenes 100 Eratosthenes a 2 2 b 3 c 5 d 7 e 100 a b c d

8 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 e Eratosthenes Eratosthenes #include <stdio.h> #include<conio.h> #define MAXNUM 1000 int main() int i,j,c=0; int prime[maxnum+1]; for(i=2;i<=maxnum;i++) prime[i]=1; for(i=2;i*i<=maxnum;i++) if(prime[i]==1) for(j=2*i;j<=maxnum;j++) if(!prime[j]) continue; if(j%i==0) prime[j]=0; for(i=2;i<maxnum;i++) if(prime[i]==1) // 1000 // 1 i // j

9 第 2 章神奇的質數 printf("%4d ",i); c++; if(c%10==0) printf("\n"); 10 printf("\n %d ",c); getch(); 已被證明的質數定理 1. 在 (a,2a] 之間必有一個質數 1 a 2 (a, 2a] (a, 2a] 2. 存在任意長度的質數等差數列 等差數列 :

10 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 K K K= K= Annals of Mathematics 3. 其他已證明的質數定理 一個偶數可以寫成兩個數字之和, 其中每一個數字最多只有 9 個質因數 一個偶數必定可以寫成一個質數加上一個合數, 其中的因數個數有上界

11 第 2 章神奇的質數 一個偶數必定可以寫成一個質數加上一個最多由 5 個因數所組成的合數 後來, 有人簡稱這個結果為 (1+5) 一個充分大偶數必定可以寫成一個質數加上一個最多由 2 個質因數所組成的合數, 簡稱為 (1+2) 什麼是孿生質數 (3, 5) (5, 7) (11, 13) (17, 19) (29, 31) (41, 43) (59, 61) (71, 73) 孿生質數的公式 Q Q+2 Q+2 Q Q

12 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 Q =P1M1+B1 =P2M2+B2 = =PKMK+BK P1 P2 P k B i 0 B i P i 2 Q<(P K+1) 2 2 Q Q+2 Q 0 P i-2 Q 2M 3M+1 5M+3 7M+5 P im i 2 Q+2 Q=29 29 = (2M+1) =3 9+2 (3M+2) =5 5+4 (5M+4) k=3 B 0 B i P i Q 2=14 餘 1 Q 3=9 餘 2 Q 5=5 餘 Q

13 第 2 章神奇的質數 中國剩餘定理 , 5, 8, 11, 14, 17, 20, 23, 26, 5 3 3, 8, 13, 18, 23, 28, n

14 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 n , 23, 38, 7 2 2, 9, 16, 23, 30, 孿生質數分佈情況 =1073 Euclid #include <stdio.h> #define MAXNUM int main() //

15 第 2 章神奇的質數 long i,j,c=0,twin=2,t=0; char prime[maxnum+1]; prime[0]=0; prime[1]=0; for(i=2;i<=maxnum;i++) prime[i]=1; for(i=2;i*i<=maxnum;i++) if(prime[i]==1) for(j=2*i;j<=maxnum;j++) if(!prime[j]) continue; if(j%i==0) prime[j]=0; for(i=2;i<maxnum;i++) if(prime[i]==1) c++; if(i-2==twin) printf("(%d,%d) ",twin,i); t++; if(t%5==0) printf("\n"); twin=i; // 1 // j printf("\n %d %d ",c,t); getch();

16 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 MAXNUM MAXNUM MAXNUM RSA RSA RSA RSA RSA 什麼是 RSA Key Key Key

17 第 2 章神奇的質數 明文 密文 密鑰 key 密鑰 key 密文 明文 Key Key Key Key PK SK 明文 密文 公鑰 key 公鑰 key 密文 明文 RSA