Sieve of Eratosthenes prime number finder up to n in C++

Question

I'be been learning c++ recently and as an exercise I wanted to write a program to find numbers up to n using sieve of Eratosthenes.

I'm new to c++ and programming in general so I'm not sure if this is wildly inefficient or not. I would love some feedback for my code performance wise or better programming practices in general.

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


int square(int a){
    return a*a;
}


int main(){

    cout << "Enter a number ";
    int MAXIMUM;
    cin>> MAXIMUM;
    int sqrtMaximum = 0;

    //populate allPrimes from 1-MAXIMUM
    vector<int> allPrimes(MAXIMUM);
    for(int i = 1; i<MAXIMUM; i++){
        allPrimes[i] = i;
    }

    //get the square root closest to MAXIMUM (>=)
    if(square(sqrt(MAXIMUM)) < MAXIMUM){
        sqrtMaximum = sqrt(MAXIMUM)+1;
    }
    else{sqrtMaximum = sqrt(MAXIMUM);}


    vector<int> primesOfSqrt = {2,3};

    //adding numbers to list of prime numbers under sqrt
    bool prime = true;
    for(int i = 3; i<sqrtMaximum; i+=2){
        prime = true;
        for(int x : primesOfSqrt){
            if(i % x == 0){
                prime = false;
                break;
            }
        }
        if(prime){
            primesOfSqrt.push_back(i);
        }
    }
    for(int x:primesOfSqrt){cout<<x<<"|||||";}cout<<endl;//print prime numbers under sqrt

    //removing multiples of the prime numbers found under the sqrt
    int factor = 0;
    allPrimes[1] = 0;
    for( int j : primesOfSqrt){
        factor = MAXIMUM/j;
        for(int x = 2; x <= factor; ++x){
            allPrimes[j*x] = 0;
        }
    }
    for(int x = 1; x<MAXIMUM; x++){
        if(allPrimes[x]!=0){cout<<allPrimes[x]<<'\t';}
    }
    char ch; cin>>ch;
}

I used 2 vectors to keep track of prime numbers, one for prime numbers less than the sqrt of n and another to remove multiples of those prime numbers, which I did by setting it to 0, but for bigger numbers i would be setting certain indexes to 0 multiple times, which would only increase the bigger the number gets. I'm not sure how to go about optimizing it or if using a different container would be best so any pointers there would be appreciated as well.

lastly I'm not sure if I am actually doing sieve of eratosthenes right, I'm pretty sure I am, but if I'm not I would like to know.

Answer 1

You asked for better programming practices, so here you go.

1. Do not use using namespace std;, it can lead to hard-to-spot name hiding errors. Read Why is “using namespace std” considered bad practice? for more information.

2. Be more generous with horizontal white space. Lines like cout<<x<<"|||||"; are hard to read and do not gain you any advantage over std::cout << x << "|||||";.

3. Do not try to fit more than one statement into one line. Things like else{sqrtMaximum = sqrt(MAXIMUM);} are usually discouraged because they are ugly and hard to read. Putting sqrtMaximum = sqrt(MAXIMUM); onto its own line is not going to hurt your code.

4. All caps variable names are unusual to say the least; most of the time all caps style is only used with macros. Thus, MAXIMUM should probably be maximum.

5. Do not use int for everything. One reason for this is that int can overflow and cause undefined behavior, the other is that your code should also express the intent it was written with. Since int is a signed type, you imply that a user could also enter -1 or any other negative number for MAXIMUM, and also that some prime numbers could be negative (Why else would allPrimes be of type vector<int>?). If you are only dealing with positive integers, use unsigned (but be aware to not decrement past 0).

Answer 2

What you are doing here is first calculating primes under sqrt and then crossing out the multiples like sieve says. However the standard approach is to calculate primes as you go and cross out multiples of each prime :

vector<bool> isPrime(MAXIMUM, true);   //we only need bool, less memory usage

isPrime[0] = false;
isPrime[1] = false;

for (int i = 4; i < MAXIMUM; i+=2) { // even numbers are handled first for efficiency
    isPrime[i] = false;
}

for(int i = 3; i < MAXIMUM; i+=2){
    if (isPrime[i]) {
        //the usual is for(int j = i * 2; j < MAXIMUM; j += i) { but I am using a bit more optimized loop
        for(int j = i * i; j < MAXIMUM; j += 2 * i) {
            isPrime[j] = false;
        }
    } 
}

for(int x = 1; x<MAXIMUM; x++){
    if(isPrime[x]){cout<< x <<'\t';}
}

This way code is much shorter and if you try it, also much faster.