Ehrlich sieve + Euler sieve + interval sieve

Ethmoid   O(nloglogn)

       The meaning of Ehrlich sieve is very simple , Every time I enumerate the prime numbers I have traversed now , Enumerate all its multiples in the interval , These enumerated numbers are composite numbers , When we enumerate the multiples of all primes in the interval , Mark them all , What is not marked is prime . This also ensures that the next enumeration must be prime , Because the composite number has been marked .

void getp()
{
	int cnt=0;
	vis[1]=1;
	for(int i=2;i<=n;i++)// enumeration 
		if(vis[i]==0)// Judge whether it is a prime 
			for(int j=2;j*i<=n;j++)// Enumerating multiples 
				vis[i*j]=1;
	return ;
}
/*
vis Marked as 1 Is not a prime number , Note that after the expansion of the Ehrlich sieve is the interval sieve 
*/

But there is a disadvantage of the sieve , We enumerate prime multiples every time , Will produce repeated enumeration , For example, a number is a multiple of some primes , The enumeration will be repeated several times . If we can eliminate duplicate enumeration , Under this premise , Created the Euler sieve .

Euler screen   O（N）

         The meaning of Euler sieve is optimized Ehrlich sieve . Every time we judge whether a number is prime , Then enumerate , But its European code is that each number will be enumerated only once . When the current number is divided by the prime factor of the traversal , We need to pay attention to , This number has been enumerated , direct break that will do .

void getp()
{
	int cnt=0;
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0)
			p[++cnt]=i;
		for(int j=1;j<=cnt&&p[j]*i<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
				break;
		}
	}
	return ;
}

Interval sieve    The time complexity is similar to that of the sieve

Interval sieve is a variant of Ehrlich sieve , It is for a certain value , But the algorithm for solving the prime number problem in the interval whose length is still within the calculation range . We first have to enumerate 2 To The prime number of . Then use these prime numbers to enumerate in the interval [L,R] Multiple of , The multiples of these enumerations are composite numbers , Mark directly , What is not marked in the interval is prime .

void segment_sieve(int a,int b)
{
    for(int i=0;i<1e6+5;i++)
     isprime[i]=lowisprime[i]=true;
        for(int i=2;i*i<b;i++)
        {
            if(lowisprime[i])
             {
                for(int j=2*i;j*j<b;j+=i)
                     lowisprime[j]=false;
                for(long long j=(a/i)*i;j<b;j+=i)
                     if(j>=a&&j<b)
                         isprime[j-a]=false;
            }
        }
}