Sieve

时间:2021-09-10 04:44:24   收藏:0   阅读:42

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 ,

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 :

\[i=prime[j]*x\quad\&\&\quad prime[j]<i \]

\[prime[k](k>j)*i \]

\[=prime[k]*prime[j]*x \]

        ,why not use

\[prime[j]*another \ number \]

        to mark it ?

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

Otherwise ,

\[i=p_1*p_2*...p_t \]

\[i*prime[j]=p_1*p_2*...p_n*prime[j] \]

\[prime[j]<=min\{p_n\} \]

\[prime[j]<=min(prime[j],min\{p_n\}) \]

\[prime[j]<=min\{factors\ of \ i*prime[j]\} \]

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;
		}
	}
}

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

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!