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.