求解素數最優算法

問題： 求解自然數n以内所有素數

埃拉托色尼篩選法：假設一個數是素數， 那麼它的倍數不是素數。

是以，建立一個大小為n+1的bool類型數組prime，prime[i]為true，表示i為素數，否則為合數，先把全部奇數設為true，偶數設為false，在周遊每個奇數，将其奇數倍的數設為false。

#include <iostream>
#include <cmath>
#include <ctime>

using namespace std;

int main()
{
    int n = , cnt = ;
    scanf("%d", &n);
    bool *prime = new bool[n + ];
    clock_t start = clock();
    for (int i = ; i <= n; ++i)
    {
        prime[i] = i &  ? true : false;
    }
    clock_t finish1 = clock();
    prime[] = true;
    printf("2 ");
    for (int i = ; i <= n; i += )
    {
        if (prime[i])
        {
            for (int j = i + i + i; j <= n ; j += i + i)
            {
                prime[j] = false;
            }
            cnt++;
            cout << i;
            cnt %  ==  ? cout << endl : cout << " ";
        }
    }
    clock_t finish2 = clock();
    printf("\n運作時間：%d個CPU時鐘\n",(finish2 - start));
    printf("\n運作時間：%lf秒\n", static_cast<double>((finish2 - start) / CLOCKS_PER_SEC));//n較小（10000以内）無法正常顯示時間
    return ;
}