Highslide for Wordpress Plugin

試撰寫一int prime(int n),可用來找出第n個質數(第一個質數為2,第二個質數為3,以此類推),並以此函數找出第100個質數。

思考理路:

先把問題簡化-怎樣判定一個正整數是不是數 => 質數定義:只能被1跟自己本身整除的數 => 牛頓的因式檢驗法(若n是合成數,必有一個小於根號n的質因數。)或是「一個數不可能被大於自己一半以上的數整除(最小公因數為2)」。

   1: int is_prime(int n){

   2:     int i;

   3:     for(i=2;i<=n/2;i++)

   4:         if(n%i==0)

   5:             return 0;

   6:     return 1;

   7: } 

 

接著就是「當迴圈送來的數經判定為質數後,如何繼續找下一個質數」,因為最後還要輸出這是要找到第n個質數,所以先令k=n,用k來當做迴圈的次數控制變數,停止條件是k<=0,而每找到一個質數k就會-1;i則從最初的1開始,接續著一直+1。

   1: int order(int n){

   2:     int i=1,k=n,x;

   3:     while(k>0){ 

   4:         x=i; 

   5:         if(is_prime(i)==1){ 

   6:             k--; 

   7:             i++;

   8:         } 

   9:         else i++;

  10:     } 

  11:     printf("第 %d 個質數為:%d\n",n,x);

  12:     return x;

  13: }

 

所以最後整個完整的程式長這樣

   1: #include <stdio.h>

   2: #include <stdlib.h>

   3: #include <math.h>

   4: #include <windows.h>

   5: int order(int n);

   6: int is_prime(int n);

   7: int main(){

   8:     order(100);

   9:     system("pause");

  10:     return 0;

  11: }

  12: int order(int n){

  13:     int i=1,k=n,x;

  14:     while(k>0){ 

  15:         x=i; 

  16:         if(is_prime(i)==1){ 

  17:             k--; 

  18:             i++;

  19:         } 

  20:         else i++;

  21:     } 

  22:     printf("第 %d 個質數為:%d\n",n,x);

  23:     return x;

  24: }

  25: int is_prime(int n){

  26:     int i;

  27:     for(i=2;i<=n/2;i++)

  28:         if(n%i==0)

  29:             return 0;

  30:     return 1;

  31: } 

Related Posts with Thumbnails
留下迴響