please anyone provide me with fastest code for generating prime no.

SIEVE OF ERATOSTHENES:

```
#include<iostream>
bool arr[1000001];
int main()
{
arr[0]=arr[1]=1;
for(int i=4;i<1000001;i+=2)
arr[i]=1;
for(int i=3;i*i<1000001;i+=2)
{
if(!arr[i])
for(int j=2;i*j<1000001;j++)
{
arr[i*j]=1;
}
}
for(int i=0;i<100000;i++)
if(!arr[i])
std::cout<<i<<" ";
return 0;
}
```

hope this will help and is not related to the current long contest…

please feel free to ask ne part of the code that u may fail to understand…

NOTE:- u need to use an extended version of this algo for PRIME1…!!!

I understand you are eager to help, but please avoid providing entire codes for question like “please give me XYZ code …”.

3 Likes

u can use pollard rho algorithm regarding prime factors…

it s good and quite different…