C++ prime numbers interval

Vote count:

0

I have to write script to print prime numbers in given range. So basically I got this script.enter code here

#include <iostream>
using namespace std;
int main()
{
    int n,p,m;
    cin>>n >> m;
    int * arr;

    arr= new  int[m+1];

    for (int i=0; i<=m; i++)
    {
      arr[i]=0;
    }

    for(int i=2;i<=m;i++){
        if(arr[i]==0)
        {   p=i;
            for (int j=2;p*j<=m;j++)
            {
                arr[p*j]=1;
            }
        }
    }

    for(int i=n;i<=m;i++){if(arr[i]==0)cout<<i<<endl;}
        delete[] arr;
    return 0;
}

Everything works pretty fine (it just prints 1 as prime (easy to fix)). But when I input numbers like 1999998973 and 1999999973 it crashes with bad_alloc. I know I probably made an huge array, but I dont know how to fix it. I also tried different algorithm but it was really slow. It must be like really fast but I dont know how to do that. (It must print the interval in like 2s or so). Does anyone have an idea? Thanks

asked 1 min ago

George

1

C++ prime numbers interval