CODEWITHSUNDEEP
c++segmentation-faultg++
AbdElHameed
AbdElHameed

Reputation: 11

Segmentation fault (core dumped) with sieve algorithm

I've been trying to implement the sieve algorithm using the following code:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector <int> primes; //all the primes found
    int theLimit = 10E5;

    void sieve (vector <int> &primes, int theLimit); //declaring the function
    sieve (primes, theLimit);

    return 0;
}

void sieve (vector <int> &primes, int theLimit) {
    const int SIZE = theLimit + 1;
    bool oddNonPrimes[SIZE]; //the array that tells you that tells you if the number that represents the current index is a non-prime or not

    for (int i = 0; i < theLimit; ++i) //setting all the array indicies to false
        oddNonPrimes[i] = false;

    primes.push_back(2);

    for (int i = 3; i < theLimit; i += 2){ //start searching for primes,we start with the number 3 and check all odd numbers only
        if (!oddNonPrimes[i]){
             int currNum = i;
             primes.push_back(currNum);
             for (int factor = 2; currNum <= theLimit; ++factor){
                currNum *= factor;
                oddNonPrimes[currNum] = true;
                currNum = i;
            }
        }
    }

}

I've tried lowering the size to make sure I'm not using too much memory but it still didn't work.I've also tried searching for an answer but I haven't found any.

What could be causing the Seg fault?and why?

Upvotes: 0

Views: 120

Answers (2)

AbdElHameed
AbdElHameed

Reputation: 11

First,Sorry for wasting your time.

I should have used:

for (int factor = 2; (currNum * factor) <= theLimit; ++factor)

Instead of:

for (int factor = 2; currNum <= theLimit; ++factor)

Otherwise when the currNum is big and then multiplied by the factor,it might become larger than the limit and thus it tries to access an index beyond the array's size.

Upvotes: 0

Pardyot Shahi
Pardyot Shahi

Reputation: 499

First of all i would like to tell that the for loop which is been run for searching for all the primes should all the primes by seeing if(!oddNonPrimes[i]) is true or not should be done only for sqrt(theLimit) as it would lead to less complexity. below is a sieve method that i would like you to refer to.

#include<bits/stdc++.h>
using namespace std;

bool *primality=new bool[10000010];
long long int *p = new long long int[1000001];
int main(){
    long long count=0;
    for(long long int i=0; i<10000010; i++)
        primality[i]=true;
    for(int i=2; i<10010; i++)
        if(primality[i])
            for(long long j=i*i; j<10000010; j+=i)
                primality[j]=false;
            for(int i=2; i<10000010; i++)
               if(primality[i]){
                   p[count]=i;
                   count++;
               }
 }

This has been taken just from one of my codes . i think it would help you. :)

Upvotes: 3

Related Questions