ExceptionAbort trap: 6

[Smac89]

This is my first time using vector type. When I run this code, it gives me an exception. Can some one tell me what is wrong with it?

#include <cstdio>
#include <vector>
#include <cmath>
#define MAX 16001

using std::vector;

int main()
{
    const int Counter = 10;
    int temp = MAX;
    vector<int> Sieve(MAX, 1);
    
    printf ("Size of vector is %d\n", int (Sieve.size()));
    
    for (int C = 0; C < MAX ; C += 2)
        if (!(C % 2) && C > 0)
        {
            Sieve.at(C - 2)= 0;
            --temp;
        }
    
    bool GotMAX = false;
    
    for (int T = 3; !GotMAX ;T += 2)
        for (int A = 2, Y = (T*A); (Y+2) < MAX; ++A)
        {
            if ((Sieve.at(Y - 2)))
            {
                Sieve.at(Y - 2) = 0;
                --temp;
            }
            
            Y = (T*A);
            if (temp - Counter <= 0)
            {
                puts ("This worked!\n");
                int Prime = 2; //We know that the first prime number was 2
                int E = Counter;
                while(E > 0)
                {
                    if (Sieve.at(Prime -2))
                        --E;
                    ++Prime;
                }
                printf("%d\n", Prime);
                GotMAX = true;
                break;
            }
        }
    return 0;
}

I'm sure the code is self explanatory, but incase you don't see it immediately, it is a prime finder; and I am trying to implement the Sieve of Eratosthenes.

Thanks in advance!

[cire]

Don't used signed variables when you only want to deal with unsigned values.

There comes a point where Y is equal to 2147483646, and Y+2 is -2147483648 due to overflow when the addition is done. That means that on line 26, (Y+2) < MAX will be true when it shouldn't be, and you will access memory that is out of the bounds of your vector, Sieve in the body of the for loop.

[Smac89]

@cire

Thanks for the response, but the maximum I will be going to will be 16001 so this will not ever (never) exceed the limit of 'int'. When I look for larger numbers then I will look into more suitable variable types.

Still open for ideas guys! Why is my code not working?

[cire]

Thanks for the response, but the maximum I will be going to will be 16001 so this will not ever (never) exceed the limit of 'int'.

You just keep guessing at what your code is doing then.

It may be that it shouldn't go that high, but the fact is it does, and the reason you don't detect is that you're using the wrong type for your variables (and probably the wrong condition for your loop.)

But if you don't actually want help, I'll keep quiet. =P

[Smac89]

No, I do need help with this.

You just keep guessing at what your code is doing then.

I don't know any other way of determining the ith prime using this method other than having if check a large enough range large enough to contain that prime. If you have any ideas, I am open

[cire]

I don't know any other way of determining the ith prime using this method other than having if check a large enough range large enough to contain that prime.

Using a sieve is reasonable. But you aren't implementing it correctly, and as near as I can tell you're not making any attempt to debug it. You're just counting on the people who read these boards to do that for you.

This is the ouput for your code when I change MAX to 20:

Size of vector is 20
This worked!

22

Maybe you can trace through the logic and figure out what's going on?

[Smac89]

Finally! Still a bit slow. Finds 1millionth in 5 secs; my friend made one that finds 10 millionth in 3 secs!

#include <iostream>
#include <vector>
#define MARK 1000000//ith prime

using namespace std;

/*
 Trying to implement a prime sieve. This is a work in progress
 */

int main()
{
    const int ThisSize = MARK;
    
    vector<bool> Sieve(ThisSize, true);
    
    int counter = 0;
    bool checkingTime = false;
    
    int s = 1;
    unsigned b = 2;
    
    while (1)
    {
        unsigned w = 3;

        for (unsigned a = 2; a*b <= (unsigned)(Sieve.size()); ++b)
            if (Sieve.at(a*b - 1))
                Sieve.at(a*b - 1) = false;
        
        while (!checkingTime)
        {
            for (unsigned q = 2, Prod = w * q; Prod < (unsigned)Sieve.size() ; ++q, Prod = w * q)
                if (Sieve.at(Prod - 1))
                    Sieve.at(Prod - 1) = false;
            
            if (w > (unsigned)Sieve.size()/2)//Make sure we have checked all the values we have
                checkingTime = true;
            
            w+=2;
        }
        
        
        if (checkingTime)
            for ( ;counter < ThisSize && s < (int)Sieve.size(); ++s)
                if (Sieve.at(s))
                {
                    ++counter;
                    if (counter == ThisSize)
                    {
                        cout << s+1 <<endl;
                        break;
                    }
                }
        
        if (counter == ThisSize)
            break;
        else
        {
            checkingTime = false;
            Sieve.resize(Sieve.size() + ThisSize, true);            
        }
                
                
    }
        
    return 0;
}

Tweaked it a bit more, eliminated some bugs, introduced a few other bugs. Now finds 10 millionth in 14 secs!

#include <iostream>
#include <vector>
#define MARK 10000000//ith prime

using namespace std;

/*
 Trying to implement a prime sieve. This is a work in progress
 */

int main()
{
    const int ThisSize = MARK;
    
    vector<bool> Sieve(ThisSize, true);
    vector<unsigned> Helper(ThisSize, 2);
    
    int counter = 0;
    bool checkingTime = false;
    
    int s = 1;
    unsigned b = 2;
    
    while (1)
    {
        unsigned w = 3;
        int h = 0;

        for (unsigned a = 2; a*b <= (unsigned)(Sieve.size()); ++b)
            if (Sieve.at(a*b - 1))
                Sieve.at(a*b - 1) = false;
        
        while (!checkingTime)
        {
            unsigned q = Helper.at(h);
            for (unsigned Prod = w * q; Prod < (unsigned)Sieve.size() ; ++q, Prod = w * q)
                if (Sieve.at(Prod - 1))
                    Sieve.at(Prod - 1) = false;
            
            Helper.at(h++) = q;
                
            if (w > (unsigned)Sieve.size()/2)//Make sure we have checked all the values we have
                checkingTime = true;
            
            w+=2;
        }
        
        
        if (checkingTime)
            for ( ;counter < ThisSize && s < (int)Sieve.size(); ++s)
                if (Sieve.at(s))
                {
                    ++counter;
                    if (counter == ThisSize)
                    {
                        cout << s+1 <<endl;
                        break;
                    }
                }
        
        if (counter == ThisSize)
            break;
        else
        {
            checkingTime = false;
            Sieve.resize(Sieve.size() + ThisSize, true);
            Helper.resize(Helper.size() + ThisSize, 2);
        }
                
                
    }
        
    return 0;
}

[cire]

A sieve is really a very simple thing. Simplify.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <vector> #include <algorithm> #include <ctime> const unsigned long long limit = 10000000 ; bool isPrime[limit] ; int main() { std::fill(isPrime, isPrime+limit, true) ; isPrime[0] = isPrime[1] = false ; std::clock_t begin = std::clock() ; unsigned primesFound = 0 ; unsigned long long num = 2 ; while ( num < limit ) { ++primesFound ; for ( unsigned long long n = num+num; n < limit; n += num ) isPrime[n] = false ; while ( ++num < limit && !isPrime[num] ) ; } std::clock_t end = std::clock() ; std::cout << "Time to calculate: " << static_cast<float>(end-begin) / CLOCKS_PER_SEC << "s\n" ; std::cout << "Expected value: 664,579\n" ; std::cout << primesFound << '\n' ; }

Time to calculate: 0.203s Expected value: 664,579 664579

[Smac89]

Not bad cire, I'm gonna have to look into that when I get home.