Sieve of Eratosthenes not working beyond 200,000

Question

My C++ program to calculate all the prime numbers using sieve of Eratosthenes method stops after 200,000. But I need to calculate the primes up to 2 million. Help would be appreciated if someone could tell me where I went wrong with my code.

#include <iostream>
#include<math.h>
using namespace std;

void isprime(long long int prime[],long int n)
{
    for(long long int i=0;i<=n;i++)
    {
        prime[i]=1;
    }
    prime[0]=prime[1]=0;
    for(long long int i=2;i<=sqrt(n);i++)
    {
        if(prime[i]==1)
        {
            for(long long int j=2;i*j<=n;j++)
                prime[i*j]=0;
        }
    }
    for(long long int i=0;i<=n;i++)
    {
        if(prime[i]==1)
        cout<<i<<endl;
     }
}
int main()
{
    long long int n;
    cout<<"enter number";
    cin>>n;
    long long int prime[n+1];
    isprime(prime,n);
    return 0;
}

https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems — Jesper Juhl, Nov 13 '18 at 20:40
200 000 ints is a lot of memory to allocate on stack. You should probably use `std::vector` or allocate your array dynamically. — Yksisarvinen, Nov 13 '18 at 20:41
Is the argument `long int n` a typo and should be `long long int`? — Weather Vane, Nov 13 '18 at 20:43
And why are you using an array of long long to store a single bit (0/1)? — Lee Daniel Crocker, Nov 13 '18 at 20:43
This `long long int prime[n+1];` is not valid C++, and even for the few compilers that support it as an extension will overflow the stack. — , Nov 13 '18 at 20:44
@Chrstian Very unfortunately, GCC supports VLAs in C++ as an extension that is enabled by default. Why? God only knows - they are optional in modern C. — , Nov 13 '18 at 20:45
@NeilButterworth Bleh. Does it at least add a warning telling you it is using an extension? — Christian Gibbons, Nov 13 '18 at 20:51
@Christian Nope. You need to compile with `-pedantic` to get that. — , Nov 13 '18 at 20:59
What *exactly* do you mean when you say it "stops after 200000"? Does it crash, does it give you unexpected results, or something else? — dbush, Nov 13 '18 at 20:59
@NeilButterworth Not perfect, but I'm okay with it. It's only unfortunate that subset of coders to not be aware that VLAs aren't part of the language will likely not be compiling with `-pedantic`. — Christian Gibbons, Nov 13 '18 at 21:22
"2,00,000" is likely to be confusing to some readers. "200,000" is more common, at least outside India. — Keith Thompson, Nov 13 '18 at 21:33
My version of your code worked past 300,000, but seg faulted well before 2,000,000. After changing prime[] from long long int, to uint8_t, it appeared to complete reasonably. The last three prime values reported: 1999969 1999979 1999993. (in less than 1 minute). Two warnings about sqrt() conversions. So perhaps your problem is related to stack size and the vla size with 2 million 8 byte values (using only 1 bit ) — 2785528, Nov 13 '18 at 22:05
do you really want to output all the primes like that? you are measuring the time to compute *and* the time to print them all out, together. change the last loop to only print out the few last primes. — Will Ness, Nov 14 '18 at 08:57
your code, with `int` instead of `long long int`, printing out only few last primes, [takes 0.01s](https://ideone.com/DB28Yq) for primes under 2000000. — Will Ness, Nov 14 '18 at 09:05

President James K. Polk · Answer 1 · 2018-11-15T05:10:05.087

2

Since each sieve element contains only a 0 or 1, there is no need to use a long long int to store each one. std::vector<bool> potentially uses 1 bit per element and thus is optimal for memory efficiency.

Here is your code with a very few modifications to use a std::vector<bool>. Since some bit manipulation is required to get and set individual elements, this version may be slower than code which uses one byte or int per sieve element. You can benchmark various versions and decide the right trade-off for your needs.

#include <cmath>
#include <cstddef>
#include <exception>
#include <iostream>
#include <string>
#include <vector>


// returns the number of primes <= n
long isprime(long n) {
    std::vector<bool> prime(n + 1);
    for (long i = 0; i <= n; i++) {
        prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    long upper_bound = std::sqrt(n);
    for (long i = 2; i <= upper_bound; i++) {
        if (prime[i] == 1) {
            for (long j = 2; i * j <= n; j++)
                prime[i * j] = 0;
        }
    }
    long num_primes = 0;
    for (long i = 0; i <= n; i++) {
        if (prime[i] == 1) {
            ++num_primes;
//          std::cout << i << std::endl;
        }
    }
    return num_primes;
}

int main() {
    std::cout << "Enter the sieve size: ";
    std::string line;
    std::getline(std::cin, line);
    std::cout << std::endl;
    long len = std::stol(line);
    long num_primes = isprime(len);
    std::cout << "There are " << num_primes << " primes <= " << len << std::endl;
    return 0;
}

edited Nov 15 '18 at 05:10

answered Nov 15 '18 at 04:38

President James K. Polk

40,516
21
95
125

Shouldn't it be one **byte** per element instead of one bit? Also, I think `char` is guaranteed to be of size 1 whereas `bool` isn't. I have seen popular SoE implementations that use `std::vector` for the sieving vector. – Joseph Wood Nov 15 '18 at 04:52
@JosephWood: I don't believe the standard *requires* `std::vector` to be one bit per element, but every implementation I've come across does it that way. See for example [this](https://en.cppreference.com/w/cpp/container/vector_bool) discussion. – President James K. Polk Nov 15 '18 at 05:06
I think you are missing the larger point. You are saying **bit** when you mean **byte**. You need something like `std::bitset` to actually utilize individual bits. To my last comment, the standard does not guarantee that `bool` has to satisfy `sizeof(bool) == 1`. The only guarantee is that `sizeof(char) <= sizeof(bool)`. See here : https://stackoverflow.com/q/9560029/4408538 – Joseph Wood Nov 15 '18 at 05:18
@JosephWood: I think you are missing the point, and not reading the link I provided. I am saying bit when I mean bit. The sizeof(bool) has no bearing on how std::vector is implemented. Again, read the discussion [here](https://en.cppreference.com/w/cpp/container/vector_bool). – President James K. Polk Nov 15 '18 at 15:02
my mistake. That is quite interesting. Thanks for being patient. As an aside, I did a little research comparing `std::vector` and `std::vector` and it seems that there are some advantages to both implementations. See here: https://stackoverflow.com/a/41761131 – Joseph Wood Nov 15 '18 at 15:21
1

I just wanted to let you know that I have been experimenting quite a bit with `std::vector / std::vector` and found that they behave rather differently. Sometimes, the `char` version is much faster, while the `bool` version can be almost twice as efficient in certain situations. Thanks for opening my eyes to this topic! – Joseph Wood Nov 24 '18 at 15:28

Sieve of Eratosthenes not working beyond 200,000

1 Answers1