-2

Using a variant of sieve of eratosthenes I wrote a piece of code in c++ which ought to calculate prime numbers and store them in a vector.
In the first part i took array ar of length 1000 using calloc() so that i get the values initialized as false of every array element and calculated and stored primes less than 1000 in the vector a.
In the second part I took values start and end , so that I'll find next prime numbers in range [start,end).
The code is working fine to calculate prime numbers (0,10000) but is giving runtime error if range to find prime numbers is greater than that.
Below is my code.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    bool *ar=(bool*)calloc(1000,sizeof(bool));
    vector<int> a;
    for(int i=2;i<1000;i++)
    {
        if(!ar[i])
        {
            a.push_back(i);
            for(int j=i*i;j<1000;j+=i)
                ar[j]=true;
        }
    }
    int start=1000,end=2000;
    while(start<10000)
    {
        for(int i=0;i<1000;i++)
            ar[i]=false;
        for(int i=0;i<a.size();i++)
        {
            int m=start/a[i];
            if(start%a[i]>0)
                m++;
            for(int j=a[i]*m;j<end;j+=a[i])
                ar[j-start]=true;
        }
        for(int i=0;i<1000;i++)
        {
            if(!ar[i])
            {
                a.push_back(i+start);
                for(int j=(i+start)*(i+start);j<end;j+=i+start)
                    ar[j-start]=true;
            }
        }
        start+=1000;
        end+=1000;
    }
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<' ';
    return 0;
}
Sc00by_d00
  • 65
  • 1
  • 11
  • Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Some programmer dude Apr 21 '18 at 08:59
  • 1
    As for your problem, please [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Some programmer dude Apr 21 '18 at 08:59
  • This code is full of terrible practices... Including [`#include `](https://stackoverflow.com/q/31816095/9254539), [`using namespace std`](https://stackoverflow.com/q/1452721/9254539), and messing with dynamic memory allocation when you clearly know about the existence of `std::vector`. – eesiraed Apr 21 '18 at 17:38

1 Answers1

0

I recommend static declaration of array ar bool ar[1000]; and then put assertion before accessing array ar, since there is some issue with your calculation. When you run your code, your IDE will stop before writing outside the array boundaries

a.push_back(i+start);
for(int j=(i+start)*(i+start);j<end;j+=i+start)
{
  assert(j-start >= 0 && j-start < 1000);
  ar[j-start]=true;
}
gabonator
  • 391
  • 1
  • 9