Eratosthenes筛

忘是亡心i 2023-03-05 09:46 17阅读 0赞

## 什么是Eratosthenes筛？ **(**What is Sieve of Eratosthenes?**)** ##

**Sieve of Eratosthenes** is an ancient algorithm of finding prime numbers for any given range. It's actually about maintaining a Boolean table to check for corresponding prime no.

**Eratosthenes的筛子**是一种古老的算法，可以找到任何给定范围的质数。 实际上，这是关于维护布尔表以检查相应的素数。

### 算法 **(**Algorithm**)** ###

The algorithm is pretty simple.

该算法非常简单。

1.  Say, we need information up to integer **N**.
    
    假设我们需要最大为**N的信息** 。
2.  Create a table of **size N+1, sieve\[N+1\]**
    
    创建一个**大小为N + 1**的表**，筛子\[N + 1\]**
3.  Assign all the table entries **TRUE** initially.
    
    最初将所有表条目分配为**TRUE** 。
4.  Base case:
    
    基本情况：
    
    0 and 1 is not prime
    
    0和1不是素数
    
    Thus
    
    从而
    
    **sieve\[0\]=FALSE=sieve\[1\]**
    
    **sieve \[0\] = FALSE = sieve \[1\]**
5.      For(i=2; i*i<=N; i=i+1)
            IF(sieve[i] is TRUE) //i is prime
                Make all multiple ofi FALSE since they are not prime
                sieve[j]=FALSE where j is multiple of i within range N
            END IF
        END FOR
6.  Table is built. Now to check any integer **K** whether prime or not
    
    表已建立。 现在检查任何整数**K**是否为素数
    
    Return
    
    返回
    
    **sieve\[k\]**
    
    **筛\[k\]**

**Example with explanation:**

**带有说明的示例：**

Let's say our range is up to 20
        Thus initially declare sieve[21] and all are true.
        sieve[0]=FALSE
        sieve[1]=FALSE
        ------------------------------------------------------------
    
        sieve[2]=true
        Thus all multiple of 2, needed to be false
        (Of course they are not prime since divisible by 2)
        Thus,
        sieve[4]=FALSE
        sieve[6]=FALSE
        sieve[8]=FALSE
        sieve[10]=FALSE
        sieve[12]=FALSE
        sieve[14]=FALSE
        sieve[16]=FALSE
        sieve[18]=FALSE
        sieve[20]=FALSE
        ------------------------------------------------------------
    
        sieve[3]=true
        Thus all multiple of 3, needed to be false
        (Of course they are not prime since divisible by 3)
        Thus,
        sieve[6]=FALSE (it was already false though)
        sieve[9]=FALSE
        sieve[12]=FALSE(it was already false though)
        sieve[15]=FALSE
        sieve[18]=FALSE(it was already false though)
        ------------------------------------------------------------
    
        Sieve[4]=FALSE (Nothing to do more with it)
        ------------------------------------------------------------
    
        sieve[5]=TRUE
        Thus all multiple of 5, needed to be false
        (Of course they are not prime since divisible by 5)
        Thus,
        sieve[10]=FALSE (it was already false though)
        sieve[15]=FALSE (it was already false though)
        sieve[20]=FALSE (it was already false though)
    
        In this way, after completing all possible entries we can find
        Only true entries are
    
        sieve[2]
        sieve[3]
        sieve[5]
        sieve[7]
        sieve[11]
        sieve[13]
        sieve[17]
        sieve[19]
    
        Others are false.

So now for any given number with in the **N**

所以对于**N中的**任何给定数

We can tell whether the number is prime or not in O(1) time (based on corresponding TRUE/FALSE value).

我们可以在O(1)时间内判断数字是否为质数(基于相应的TRUE / FALSE值)。

### 何时在编程中使用此算法？ **(**When to use this algorithm in programming?**)** ###

Sieve of Eratosthenes can be very efficient for any program we require to check prime numbers for multiple times (Multiple test cases too).

Eratosthenes筛网对于我们需要多次检查质数的任何程序(也可以是多个测试用例)来说都是非常有效的。

In such cases, we construct the Sieve of Eratosthenes only single time and for all query each only takes O(1) time reducing the time complexity overall.

在这种情况下，我们只构造一次Eratosthenes筛，对于所有查询，每个筛仅花费O(1)时间，从而降低了总体时间复杂度。

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        
    	int n;
    	
    	cout<<"Enter max range to check for prime numbers\n";
    	cin>>n;
    	
    	bool sieve[n+1];
    	
    	//sieve of eratosthenes
    	memset(sieve,true,sizeof(sieve));//initially all true
    	sieve[0]=sieve[1]=false;//0,1 not prime
    	for(int i=2;i*i<=n;i++)
    		if(sieve[i])
    	for(int j=i*2;j<=n;j+=i)//for multiple of i
    		sieve[j]=false;//can't be prime
    
    	cout<<"Enter non-negative integer to check prime or not\n";
    	cout<<"Negative no to exit\n";
    	
    	int k;
    	cin>>k;
    	
    	while(k>=0){
        
    		if(sieve[k])
    			cout<<k<<" is prime\n";
    		else
    			cout<<k<<" is not prime\n";
    
    		cout<<"Try more or exit\n";
    		cin>>k;
    	}
    	
    	cout<<"Exited\n";
    	
    	return 0;
    }

**Output**

**输出量**

Enter max range to check for prime numbers
    1000
    Enter non-negative integer to check prime or not
    Negative no to exit
    997
    997 is prime
    Try more or exit 
    993
    993 is not prime 
    Try more or exit 
    13 
    13 is prime 
    Try more or exit 
    103
    103 is prime
    Try more or exit 
    111
    111 is not prime 
    Try more or exit 
    -1 
    Exited

> 翻译自: [https://www.includehelp.com/icp/sieve-of-eratosthenes.aspx][https_www.includehelp.com_icp_sieve-of-eratosthenes.aspx]

[https_www.includehelp.com_icp_sieve-of-eratosthenes.aspx]: https://www.includehelp.com/icp/sieve-of-eratosthenes.aspx