這是一個基本的算法編程問題，即給定一個整數(shù)x，判斷x是否為素數(shù)。算法基本思路如下：讓x被2到sqrt(x)除,如果x能被2至sqrt(x)之中任何一個整數(shù)整除，那么說明x不是質(zhì)數(shù)，否則是質(zhì)數(shù)。原因不再說明，具體代碼如下：

#include <cmath>

bool IsPrime(int x)
{
    for(int i = 2; i <= (int)sqrt(x); i++)
    {
        if((x % i) == 0)
            return false;
    }

    return true;
}

繼續(xù)引申，從1開始的連續(xù)整數(shù)中哪些為素數(shù)？可以使用“篩選法”。所謂“篩選法”指的是“埃拉托色尼(Eratosthenes)篩法”。他是古希臘的著名數(shù)學家。他采取的方法是，在一張紙上寫上1到100全部整數(shù)，然后逐個判斷它們是否是素數(shù)，找出一個非素數(shù)，就把它挖掉，最后剩下的就是素數(shù)。具體做法如下：

<1> 先將1挖掉(因為1不是素數(shù))。
<2> 用2去除它后面的各個數(shù)，把能被2整除的數(shù)挖掉，即把2的倍數(shù)挖掉。
<3> 用3去除它后面的各數(shù)，把3的倍數(shù)挖掉。
<4> 分別用4、5…各數(shù)作為除數(shù)去除這些數(shù)以后的各數(shù)。這個過程一直進行到在除數(shù)后面的數(shù)已全被挖掉為止。例如找1～50的素數(shù)，要一直進行到除數(shù)為47為止（事實上，可以簡化，如果需要找1～n范圍內(nèi)素數(shù)表，只需進行到除數(shù)為n^2(根號n)，取其整數(shù)即可。例如對1～50，只需進行到將50^2作為除數(shù)即可。）

如上算法可表示為：

#include <iostream>
#include <cmath>
//#include "Prime.h"

int main()
{
    int array[101];
        int i, j;

    for(i = 2; i <= 100; i++)
        array[i] = i;

    for(i = 2; i < (int)sqrt(100); i++)
    {
        if(array[i] != 0)
        {
            for(j = i + 1; j <= 100; j++)
            {
                if((array[j] != 0) && (array[j] % array[i] == 0))
                {
                    array[j] = 0;
                }
            }
        }
    }

    for(i = 2; i <= 100; i++)
    {
        if(array[i] != 0)
            std::cout << array[i] << std::endl;
    }

    return 0;
}

上述的篩選法的時間復雜度為O(sqrt(n)*n)，效果不夠理想。