Sieve

Overview

Sieve of Eratosthenes is an \(O(loglogn)\) algorithm , but it can be inefficient because a composite number may be traversed multiple times .

For example , \(20\) is going to be traversed twice at \(4*5\) and \(10*2\) .

However , for efficiency ，there‘s an algorithm called Euler‘s sieve that avoids traverse a composite number more than once by finding it only with its smallest and largest prime factors .

Main content

For an enumerated number \(i\) , multiply it by prime numbers have been found ( \(prime[j]<=i\) ) and mark the resulting composite number \(i*prime[j]\) ;

More specifically ,

• We use array \(prime[i]\) to record the prime numbers have been found .

• And for an enumerated number \(i\) , firstly find whether it have been marked or it‘s a prime ;

• If a number is composite , it is going to been marked by its factors .

• Secondly , enumerate \(prime[j]\) , mark all \(i\)‘s multiples \(i*prime[j]\) .

• We just have to enumerate the prime multiples of \(i\) , becauce the composite multiples of one number will be marked by prime multiples of another number .

• For example , only \(7*2\) , \(7*3\) , \(7*5\) ... are going to be marked because \(7*4\) are going to be marked by \(14*2\) .

• In this way we can get all the prime numbers by sieving out composite numbers .
  
  

How to ensure that a composite number is sieved out only by its smallest and largest prime factors?

The core idea is simple .

While enumerating \(prime[j]\) , we stop the enumeration after marking \(i*prime[j]\) that \(prime[j]|i\) for the first time .

Because :

• When we find that \(prime[j]|i\) , it means that :

• When we mark :

        ,why not use

        to mark it ?

• \(prime[j]\) will less than \(prime[k]\) , and \(the \ other \ number\) will greater than \(i\) .

• That means , \(prime[k]\) is no more the smallest factor and \(i\) is no more the largest factor .
  
  

Don‘t forget , we are going to find the composite numbers only with its smallest and largest prime factors .

Otherwise ,

• Do the factorization of \(i\) , we have :

• Before we find a \(prime[j]\) that \(prime[j]|i\) , because of the monotone increasing property of \(prime[]\) ,

• obviously we have :

• Thus , we have :

• That is ,

• Therefore , \(prime[j]\) is definitly the smallest factor and \(i\) is definitly is the largest factor .

So far, both adequacy and necessity have been proved .

In this way , we can ensure that a composite number is sieved out only by its smallest and largest prime factors .

Code

void getPrime(int n){
	for(int i=2;i<=n;i++){
		if(!marked[i]) prime[++SUM]=i;
		for(int j=1;j<=SUM&&prime[j]*i<=n;i++){
			marked[i*prime[j]]=1;
			if(!(i%prime[j])) break;
		}
	}
}

Sieve

原文：https://www.cnblogs.com/WHITELABS/p/Euler_Prime_Sieve.html