小编Qin*_*ang的帖子

我试图解决C ++中的编码问题，该问题计算素数的数量小于非负数的数量n。

所以我首先想出了一些代码：

int countPrimes(int n) {
    vector<bool> flag(n+1,1);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要88毫秒，并使用8.6 MB的内存。然后，我将代码更改为：

int countPrimes(int n) {
    // vector<bool> flag(n+1,1);
    bool flag[n+1] ;
    fill(flag,flag+n+1,true);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要28毫秒和9.9 MB。我真的不明白为什么在运行时间和内存消耗上都存在这样的性能差距。我已阅读相类似的问题这一个和那一个，但我仍然困惑。

编辑：我的运行时间与11.5 MB的存储器替换之后减少至40毫秒vector<bool>与vector<char>。