CODEWITHSUNDEEP
c++segmentation-fault
Jay Teli
Jay Teli

Reputation: 1032

C++ : Segmentation fault (core dumped) issue

Implementation of Sieve of eratosthenes in C++ :

When i Run my C++ program i get

"Segmentation fault (core dumped)"

It compiles without any error.

In this program , i am trying to print all prime numbers between two numbers a and b.

#include <iostream>
#include <string.h>
#define MAX 1000000

using namespace std;

// Print all primes s.t. a <= prime <= b
int main()
{
    int t; // no of test cases
    cin>>t;

    bool prime[MAX + 1];    // a[i] = true for i = prime
    long int count_primes_lte_me[MAX + 1]; // a[i] = Count ( primes ) <= i
    long int counter_of_visited_primes;

    prime[0] = prime[1] = false;
    for(int i = 2 ; i <= MAX ; i++)
    {
        if(prime[i] == true)
            count_primes_lte_me[i] = ++counter_of_visited_primes;

        for(int j = i*i ; j <= MAX ; j += i)  // sieve of eratosthenes
            prime[j] = false;
    }

    long int a , b;
    while(t--)
    {
        cin>>a>>b;
        cout<<count_primes_lte_me[b] - count_primes_lte_me[a - 1]<<endl;
    }

    return 0;
}

Upvotes: 2

Views: 1405

Answers (3)

poorgoat
poorgoat

Reputation: 47

You've a Max of a million... I tried to reduce it and no error but still nothing works... try this 

/************************************
***Array names as pointers***********
************************************/
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    const int MAX = 10000;
    long prime[MAX] = { 2, 3, 5 };
    long trial = 5;
    int count = 3;
    int found = 0;

    do
    {
        trial += 2;
        found = 0;
        for (int i = 0; i < count; i++)
        {
            found = (trial % *(prime + i)/* prime[i] */) == 0;

            if (found)
                break;
        }
        if (found == 0)
            *(prime + count++)/* prime[count++] */ = trial;
    } while (count < MAX);

    for (int i = 0; i < MAX; i++)
    {
        if (i % 5 == 0)
            cout << endl;
        cout << setw(10) << *(prime + i)/* prime[i] */;
    }
    cout << endl;
    return 0;
}

Upvotes: 1

yassin
yassin

Reputation: 652

i * i will overflow in your inner loop for i <= MAX. This might cause a segfault due to negative j. Use a larger integer type: long long j = (long long)i * i.

For correctness, you need to initialize the prime array to true and the count array to 0 values.

Upvotes: 1

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36441

Try with a smaller value for MAX. Allocating such huge arrays on the stack produces the (initial) problem. Then replace with dynamic allocation:

bool *prime = new bool[MAX+1];
if (prime==nullptr) // error

...

delete [] prime;

You may also use static allocation (define your variables as global).

Best may be to use some appropriate container, for example bitset.

Beware that i*i may overflow, so other problem may arise...

Upvotes: 4

Related Questions