# Eratosthenes Sieve Implementation

My friend and I were doing an Eratosthenes Sieve implementation, it works, but I think there is a mistake with "n" and with the first for condition ("i<=n"). I think that condition can cause a segmentation fault as there's no criba[n], am I right? Any suggestion to make it faster?

#include <bits/stdc++.h>

using namespace std;

const long long int n=1000000;
bool criba[n+1];

void gencriba(){
memset(criba,true,sizeof(criba));
criba[0]=criba[1]=false;
for(long long int i=2;i<=n;++i){ ///Aquí es donde usa <=
if(criba[i]){
for(long long int j=i;j<=n/i;++j){
criba[j*i]=false;
}
}
}
}

int main()
{
gencriba();
int c;
cin>>c;
cout<<criba[c]<<endl;
return 0;
}


Edit: Decided to change the array size to n+1, so that there's no possibility of getting an error because of invalid memory address

• Yes, you could potentially cause an invalid access error when i == n since that's 1 element past the end of the array. – user1118321 Aug 26 '17 at 2:52
• Any suggestion? Declaring the array as n+1? – Cesar Salazar Aug 26 '17 at 3:49
• Yes, either add an element to the array change the condition from i <= n to i < n. – user1118321 Aug 26 '17 at 4:21

Any suggestion to make it faster?

No, not really, it looks good as it is.

The inner loop termination condition involves division: j <= n / i. You're hoping the optimizing (-O3) compiler hoists the constant out of the loop. I'm willing to take the bet that it does get hoisted, that there's no need to explicitly assign a temp variable.

The j * i expression doesn't need to use multiplication -- addition would suffice, using something like j or n += i. Depending on details of your CPU, that might help, or not.

Depending on how far you want to take this, as with all optimizations these are all things that will be dependent on measurements

Going from array of bool to a bitarray might give you an improvement by reducing the number of times that the L2 cache has to be accessed. It depends if the amount of arithmetic you have to do is paid of by the reduced number of cache swaps

Unrolling your core loop, and doing multiple operations in a row might help dependent on what the compiler does ( there might already be some unrolling going on) this will let the CPU perform multiple longer operations at the same time.

Lastly using vector operation could also make this faster but again the logic will become more complex.

The code looks pretty good, but a few things that can get you into trouble should be addressed:

Don't #include <bits/stdc++.h>. See this answer on Stack Overflow for an explanation of why. TL;DR - it includes everything and you don't need all that it includes. It's just making your compile times take much longer than they should.

There's no need to use long long for values up to and including 1,000,000. A 32-bit long will do just fine with plenty of room in case you go over.

You should avoid global variables. In a program of this size it's no big deal, but it's a bad habit to get into. If your program grows to a larger size, it can become very difficult to reason about why and where a global variable is being changed, making it harder to find and fix bugs or to extend the application's functionality.

Be careful creating such large arrays. In this case, because they are global, they are in your program's data segment rather than on the stack so it's not an issue. However, if you were to create them on the stack in this manner, there is a chance that you could end up with a stack overflow error. 1 million bools will take up at least 1 Megabyte of memory. Many applications have a stack that is smaller than that, or only a little larger by default.

For readabliity, I recommend using more spaces in your code. In particular, I always leave a space before and after any operator. So your main() function would look more like this:

int main()
{
gencriba();
int c;
cin >> c;
cout << criba [ c ] << endl;
return 0;
}


It makes it easier to see at a glance what's a variable and how they're being operated on.

In terms of performance, the best optimization is usually a better algorithm. This Stack Overflow Question asks which algorithms are fastest and has several answers.

Apart from what the others have written, in C++ the use of C-style arrays is discouraged. It's thus preferable to use std::array instead as the type for your criba variable (since you know the size at compile time - otherwise std::vector is the equivalent). You can use it exactly the same way you do now, except you don't need to use C functions like memset() - you can use fill_n() instead. Using a standard library container also enables you to use all the algorithms of the standard library, which may make your life easier and your code cleaner.

Also, for the array of bools, std::bitset might seem like a natural choice. It's syntactically nice to use it in your case, since setting all bits to true would be just criba.set(), and printing all the values is as simple as std::cout << criba. That said, using std::array<bool> (but not std::vector<bool>) might be faster since bitset is not that good if you call operator[] and read/write individual bits' values frequently - see this thread. I don't think performance is going to be an issue in your case though. On the other hand, bitset stores bool value as 1 bit, so your data is going to take roughly 8 times less space as bitset than as bool array - it's going to make a big difference if your data gets allocated on stack. Another advantage of std::bitset is that its constructor is constexpr, so allocating it costs you nothing time-wise at runtime.

The bottom line is: consider using std::array or std::bitset for your criba variable weighing the pros and cons described above.

Last but not least, apart from making your n variable non-global as pointed out in another answer, you could also declare it as constexpr since you know its value at compile time.

You can try segmented sieve if you want to have a faster way of generating primes. Also You can try using scanf/printf instead of cin/cout ios_base ::sync_with_stdio(false) with cin/cout , but it won't matter here i guess , as your input and output is small. But still you can try.

Also you should change that n/i to j*i , its not a good practice.