prime no. generation

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…:stuck_out_tongue:

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

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

@vinayak garg ya…i’ll keep that in mind…sorry & thanks…:slight_smile:

u can use pollard rho algorithm regarding prime factors…
it s good and quite different…

//