Array like container that only stores large amounts of 1s and 0s

  arrays, bitset, c++, containers

I’m trying to make a program that tells you the amount of prime numbers between 0 and n and tell you if x is a prime number. I’ve managed to make it work with a really big array that stores bools, but i feel like i can optimize this by using something like a bitset, but when i try to use a bitset it just crashes. I need the container to be able to store 10^8 0s and 1s.

EDIT: This segfaults for large numbers 🙁

#include <iostream>
#include <algorithm>
#include <bitset>

using namespace std;

int main()
{
    unsigned int n;
    unsigned int x;
    unsigned short int q;

    cin >> n >> q;

    //bitset<10^8 - 1> primes;
    bool primes[n]{false};

    for(unsigned int i = 2; i < n; i++)
    {
        for(unsigned int j = i*i; j < n; j += i)
        {
            primes[j - 1] = true; 
            //primes.set(j - 1);
        }
    }

    primes[0] = true;
    //primes.set(0);
    cout << count(primes, primes + n , false) << endl;
    //cout << primes.count() - 1 << endl;

    for(unsigned short int i = 1; i <= q; i++)
    {
        cin >> x;
        cout << !primes[x - 1] << endl;
    }

    return 0;
} 

Source: Windows Questions C++

LEAVE A COMMENT