Prime Number finding algorithm returns weird values

Question

I am beginning to learn c++, and was working through the Project Euler challenges, and #7 asks you to find all prime numbers within a given range. After online research i decided to try using Sieve of Erastothenes, however with the code i have set up, i currently get weird values such as )2, 0) when i ask for 2 primes, and (2, 4, 5, 5) when i input 5.

#include <iostream>
#include <vector>
#include <math.h>
#include <bits/stdc++.h>

using namespace std;

int main(){

int end_point;
cout << "how many prime numbers would you like to find?\n";
cin >> end_point;

//creates a vector to store all values, that will eventually be whittled down to primes
vector<int> primes = {2};

//adds all numbers between 2 and chosen end point to the vector
for (int i = 3; i <= end_point; i++){

    primes.push_back(i);
}

for (int i = 0; i < end_point; i++){

    //starts at the first value (always 2), and feeds it into the next for loop
    //once the next loop is done, it moves on to the next value in the loop and feeds that in
    primes[i];

    //looks at values in the vector, starting with the next value in the vector
    for (unsigned int j = i+1; j < primes.size(); j++){

        //checks if the value at [j] is divisible by the value at [i]
        //if it is, this deletes it from the vecotr
        //if not, it moves on to the next value in the vector
        if(primes[j] % primes[i] == 0){

            primes.erase (primes.begin() + (j-1));
        }
        else{}
    }

//prints out all of the primes in the specified range
cout << "Primes are: ";
for (unsigned int k = 0; k <= primes.size(); k++){
    cout << primes[k] << ", ";
}
}
}

Answer 1

you can check prime from 2 to the sqrt of that number. this will omit duplicates and extra checks.

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

vector<int> getPrimes(int start, int end){
    if( start <0 || end < 0 || end < start ){
        return {};
    }
    
    int max = 0;
    bool isPrime = true;
    vector<int> prims = {};
    
    
    for( int i = start ; i <= end ; i++ ){
        max = sqrt(i);
        isPrime = true;
        for(int j = 2 ; j <= max ; j++ ){
            if( i % j == 0 ){
                isPrime = false;
                break;
            }
        }
        
        if(isPrime){
            prims.push_back(i);
        }
    }
    
    return prims;
}

int main()
{
    
    
    vector<int> prims = getPrimes(0,100);
    

    
    for(int n : prims) {
        cout << n << '\n';
    }
    
    return 0;
  
}

Sqrt Reason:

imagine you want to find out that 17 is a prime number or not. the simplest way is to loop from 0 to 17 to check its multiples. but it doesn't needed to do that. the sqrt of 17 is almost 4. so you check the multiples until the number 4. the next number is 5. from 5 to 17, all the multiples that their results is smaller that 17 is from 4 to 0. because 5 * 5 is 25 . even 5 * 4 is 20. so all multiples going to be repetitious. now you can just check multiples from 2 to square root of that number to find out the number is a prime number or not

Answer 2

You shouldn't remove element from array when you traverse it. You can try it by marking. example：

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {

    int end_point;
    cout << "how many prime numbers would you like to find?\n";
    cin >> end_point;

    //creates a vector to store all values, that will eventually be whittled down to primes
    vector<int> primes = { 2 };

    //adds all numbers between 2 and chosen end point to the vector
    for (int i = 3; i <= end_point; i++) {

        primes.push_back(i);
    }

    for (int i = 0; i < end_point; i++) {

        //starts at the first value (always 2), and feeds it into the next for loop
        //once the next loop is done, it moves on to the next value in the loop and feeds that in
        int val = primes[i];

        // to ensure the value is not zero
        if (val == 0)
            continue;

        //looks at values in the vector, starting with the next value in the vector
        for (unsigned int j = i + 1; j < primes.size(); j++) {

            //checks if the value at [j] is divisible by the value at [i]
            //if it is, this deletes it from the vecotr
            //if not, it moves on to the next value in the vector
            if (primes[j] > 0 && primes[j] % val == 0) {
                // set the value zero to element of array.
                primes[j] = 0;
            }
        }

        //prints out all of the primes in the specified range
        cout << "Primes are: ";
        for (unsigned int k = 0; k <= primes.size(); k++) {
            if (primes[k] > 0) // output the value which greater then zero.
                cout << primes[k] << ", ";
        }
    }

    return 0;
}

Answer 3

1. You delete wrong element. This is right:

   primes.erase(primes.begin() + j);

2. Your last loop in wrong place. Take it out of previous 'for loop'. And you go after last element. Should be:

   k < primes.size();

not

k <= primes.size();

=== Now it works properly ===

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {

    int end_point;
    cout << "how many prime numbers would you like to find?\n";
    cin >> end_point;

    vector<int> primes = { 2 };

    for (int i = 3; i <= end_point; i++) {
        primes.push_back(i);
    }

    for (int i = 0; i < end_point; i++) {
        for (unsigned int j = i + 1; j < primes.size(); j++) {
            if (primes[j] % primes[i] == 0) {
                primes.erase(primes.begin() + j);
            }
            else {}
        }
    }
    cout << "Primes are: ";
    for (unsigned int k = 0; k < primes.size(); k++) {
        cout << primes[k] << ", ";
    }
    return 0;
}