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…