輸出200以內的素數

本文將從算法原理、代碼實現、優化等方面詳細闡述如何輸出200以內的素數。

一、算法原理

求解素數的算法有許多，比如試除法、埃氏篩法、歐拉篩法等。這裡我們介紹一種簡單易懂的算法——試除法。

試除法的基本思想是：對每個待判定的數，用小於它的數去除，如果不能被整除，則為素數。

根據試除法，我們可以得到200以內的素數流程如下：

int i,j;
for(i=2;i<=200;i++)
{
    for(j=2;j=i)
        printf("%d ",i);
}

代碼中，外層循環i從2開始枚舉200以內的數。內層循環j從2到i-1，如果存在任一j，使得i%j==0，即i能被j整除，則跳出內層循環。否則，i為素數，輸出i。

二、代碼實現

參考算法原理，我們可以用C語言來實現輸出200以內的素數：

#include<stdio.h>
int main()
{
    int i,j;
    for(i=2;i<=200;i++)
    {
        for(j=2;j<i;j++)
        {
            if(i%j==0)
                break;
        }
        if(j>=i)
            printf("%d ",i);
    }
    return 0;
}

代碼中，定義兩個變量i和j，分別表示待判定的數和用來試除的數。i從2開始枚舉，j從2到i-1，如果存在任一j，使得i%j==0，即i能被j整除，則跳出內層循環。否則，i為素數，輸出i。

三、優化措施

上述代碼雖然實現了輸出200以內的素數，但在容量更大的情況下性能會受到影響。接下來，我們介紹幾種優化措施，能夠提高程序的效率。

3.1 減少重複計算

試除法中重複計算是一個比較浪費時間的地方，每次都要重複從2到i-1枚舉j，計算i%j==0。當然，我們可以通過開一個數組，存儲已經測試過的值，避免重複計算。數組存儲後，下一次判斷素數時，只需要使用已經存儲的素數進行試除。

#include<stdio.h>
#define MAX 200
int main()
{
    int i,j,count=0;
    int a[MAX]={0};
    for(i=2;i<=MAX;i++)
    {
        if(a[i]==0)
        {
            printf("%d ",i);
            count++;
            for(j=i*i;j<=MAX;j+=i)
                a[j]=1;
        }
    }
    printf("\n200以內的素數數量為：%d\n",count);
    return 0;
}

代碼中，定義了一個MAX常量，用於定義數組長度。利用數組實現素數的判定，數組a初始化為0，表示所有的數都是素數。從2到MAX枚舉i，如果a[i]==0，表示i為素數，輸出i；同時更新數組a，將i的所有倍數都標記為合數（a[j]=1）。count變量用於存儲素數的數量。

3.2 減少除數的枚舉範圍

既然我們要判斷i是否為素數，那麼符合以下兩個條件的數j，就不必再進行試除操作，從而減少程序的運算量。

1. j從2到i-1枚舉；

2. j*j<=i。

#include<stdio.h>
#define MAX 200
int main()
{
    int i,j,count=0;
    int a[MAX]={0};
    for(i=2;i<=MAX;i++)
    {
        if(a[i]==0)
        {
            printf("%d ",i);
            count++;
            for(j=i*i;j<=MAX;j+=i)
                a[j]=1;
        }
    }
    printf("\n200以內的素數數量為：%d\n",count);
    return 0;
}

代碼中，內層循環的條件變為j*j<=i，從而減少了循環次數，優化了程序的速度。

四、總結

本文介紹了輸出200以內的素數的算法原理、代碼實現和優化措施。試除法可以簡單易懂地求解素數，但因為重複計算和循環次數過多，影響了程序效率。通過數組存儲和減少除數枚舉範圍等優化措施，不僅提高了程序的速度，而且減少了不必要的運算。