用向量创建 SIEVE

Question

我正在尝试用向量制作一个简单的筛子：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<int> myVector;

void vec_sieve()
{
    myVector.push_back(0);
    myVector.push_back(0);

    unsigned int sz = pow(2,31);
    for(unsigned int i=2;i<sz;i++)
    {
        myVector.push_back(1);
    }

    int len = sqrt(sz);
    for(unsigned int i=2;i<=len;i++)
    {
        if(myVector[i] == 1)
        {
            for(unsigned int j=2;i*j<=sz;j++)
            {
                myVector[i*j] = 0;
            }
        }
    }
}

int main()
{   
    vec_sieve();
    int n;
    cin>>n;
    unsigned int input;

    for(int i=0;i<n;i++)
    {
        cin>>input;
        if(myVector[input] == 1)
        {
            cout<<"Prime"<<endl;
        }
        else
        {
            cout<<"Not Prime"<<endl;
        }
    }

    return 0;
}

我是矢量的新手，正在尝试使用 seive 创建素数矢量，但不知何故我得到了 Bad_Alloc
任何人都可以具体说明这个错误的分配吗？
提前致谢

Answer 1

std::bad_alloc 可能会被抛出，因为您正试图在虚拟内存中分配一个连续的内存块，该内存块太大而无法容纳其任何 "gaps".

unsigned int sz = pow(2,31); // too large

2^31 乘以 4 个字节（int 的大小）是 8 gb。在调整数组大小时，您应该始终首先考虑 "how much memory does it allocate" 。此外，bool 足以包含 1 和 0。 vector<bool> 进一步优化内存。

与您的代码相关的一些其他观察结果：

而不是这个：

for(unsigned int i=2;i<sz;i++)
{
    myVector.push_back(1);
}

使用这个：

myVector.resize (sz, 1);

用向量创建 SIEVE

Creating SIEVE with vectors

c++

vector

sieve