Stuck - Need some Guidance

[joshrod921]

Hello everyone, Im currently working on an assignment for school, and I have to implement the Sieve of Eratosthenes to find all prime numbers in my program between the ranges of the numbers 2 and 300.

Im having a lot of trouble with the algorithm itself. I've been at it for nearly two days straight, and I'm starting to feel incapable of doing it. I've looked at a lot of different code to get some ideas. However I can't seem to implement it correctly.

I need to use the .erase( .begin( ) + n ) function to delete the numbers from a vector in the program.

It seems to work "okay for the first 5 numbers, but after that it fails miserably.

void Eratos (int length, vector <int> &p_list)

{
    // generate list of numbers up to specified length
    
    for (int number = 2; number <= length; ++number)
        
        {
            p_list.push_back(number) ;
        }
    
    for(int index = 0; index < p_list.size(); index++)
        
        {
            if(p_list[index])
                
                {
                    for(int i = p_list[index]; i < p_list.size(); i++)
                        
                        {
                                p_list.erase( p_list.begin() + i );
                        }
                    
                }
        }
    
    for (int index = 0; index < p_list.size(); index++)
        
    {
        cout << p_list[index] << endl;
    }

}

As you can see i created two for loops, and one is inside the other. For the second for loop i set the variable i equal to the value of the element being used.

The loop is supposed to accomplish something like this:

let i in the inner loop be equal to the value of the first element in the vector ( 2 ).

Start from the beginning of the vector and count twice over.

it always resets back to the beginning of the vector after completing a loop, and counts with the new increment.

So: Let assume a range from 2 - 10

Original vector :2 3 (4) 5 6 7 8 9 10

4 is deleted.

2 3 5 6 7 8 9 10

then i increments to 3

2 3 5 (6) 7 8 9 10

10 is deleted;

then i increments to 4;

2 3 5 7 (8) 9 10

8 is deleted and so on.

as i increases, the p_list.size() decreases so that way it eventually becomes equal to p_list.size and the loop stops, then repeats with the next element value.

Any suggestion would be great, thanks and sorry for the long read.

[stahta01]

Is there a reason you think the "Sieve of Eratosthenes" can be done using delete/erase?

Note: The only way I can see it working is using a search feature. (C Programmer here)

Does the type of C++ class you are using support searching for value?
If yes, I would use that search feature or write a search method.

Tim S.

[joshrod921]

Well, the assignment requires me to use deletion of vectors, I don't have much of a choice in the matter unfortunately. Im still new to C++ so i don't know to much about classes yet. I tried writing a different version of the function to check and see if each element is a multiple of the index being compared to, it it was then i would delete it, but i ran into problems with that as well, since the function .erase( .begin() + n) starts at the beginning of the vector.

[jimblumberg]

I recommend you run the program with your debugger, set a breakpoint at the start of the second loop, then single step through the loop watching the variables as you step.

Jim

[joshrod921]

Hey guys, sorry for not responding the past few days. I was able to figure out the assignment finally. The answer was in my face the whole time, and I was just over thinking for the most part. Thanks for all the input you guys gave me!