求解素数最优算法

问题： 求解自然数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 ;
}