sieve of eratosthenes

[vince1981]

I'm writing a code to calculate the sum of the primes below a given number. I've already written a brute force program that works perfectly but is slow, so I'm trying to do a sieve of eratosthenes.

My current code gives me the right answer and displays all my outputs until somewhere between 20,000 and 25,000, at which point it doesn't display my final output and the "sum" displayed on the right starts to be incorrect. In either case, I'm getting the message "Process terminated with status -1073741819 (2 minutes, 34 seconds)." Ultimately, I'd like to calculate the sum of all the primes lower than 2 million.

Anyone have any idea where I'm going wrong?

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

using namespace std;

int main()
{
    long long upper_limit, current_position, sum=0, working_position, working;

    cout<<"Enter a number."<<endl;
    cin>>upper_limit;
    cout<<endl;

    vector<bool> sieve(upper_limit, true);
    sieve[0]=false;

    for (current_position=1; current_position<upper_limit; current_position++)
    {
        if (sieve[current_position])
        {
            sum=sum+current_position+1;
            working=current_position+1;
            cout<<working<<"   "<<sum<<endl;

            working_position=current_position;

            do
            {
                working_position=working_position+working;
                if (!sieve[working_position])
                {
                    continue;
                }

                else
                {
                    sieve[working_position]=false;
                }
            }
            while (working_position<upper_limit);
        }

        else
        {
            continue;
        }
    }

    cout<<"The sum of all prime numbers that are less than "<<upper_limit<<" is "<<sum<<"."<<endl;

    return (0);
}

[ne555]

You should remove the fat.

            do
            {
                working_position=working_position+working;
                //out of bounds
                if (!sieve[working_position])
                {
                    continue;
                }

                else
                {
                    sieve[working_position]=false;
                }
            }
            while (working_position<upper_limit);

[vince1981]

So this is my first time using vectors, and I have no idea what "out of bounds" means. Also, does the comment apply to the line above it or below it (and, incidentally, is there a "best practice" for putting comments either before or after the code they describe)?

And by "remove the fat," do you mean "just include the relevant code" or "your program only needs the following"? If it's the first, I included it all b/c I don't know where the problem is.

Thanks,

-Vince

[Silvermaul]

Out of bounds means that you try to access an element out of the bounds of the vector, i.e., that element does not exist.

As for the fat you got it right.

[vince1981]

Is this a matter of syntax? What I want to do is continue if the value stored in sieve[working_position] is false. I revised to

if (sieve[working_position]==false)

but got the same error.

Or, despite my best efforts, is my do-while loop somehow going one more time than it ought?

Thanks,

-Vince

[vince1981]

Thanks for the tips. I changed a few things around and got everything working with no errors.

Final results with the brute force method: 4 min 46 sec
Final results with the sieve: .354 sec

Both give the same final output.

You folks on this board are awesome.

Here's the relevant code (minus the fat, hopefully):

    for (current_position=1; current_position<upper_limit; current_position++)
    {
        //if sieve[current_position] is true...
        if (sieve[current_position])
        {
            sum=sum+current_position+1;
            working=current_position+1;
            working_position=current_position;

            for (working_position+=working; working_position<upper_limit; working_position+=working)
            {
               if (!sieve[working_position])
                {
                    continue;
                }

                else
                {
                    sieve[working_position]=false;
                }
            }
        }
    }

[ne555]

/*               if (!sieve[working_position])
                {
                    continue;
                }

                else
                {
                    sieve[working_position]=false;
                }*/
                sieve[working_position]=false;

The result is the same, but I think it is more clear.