[数据结构与算法]【基础算法补全】埃氏筛

算法思想：

? ? ? ? - 素数的倍数必不是素数

代码实现：

?C++：

bool *is_Prime; // 布尔型指针，用于申请一个连续的数组空间，判断数组下标对应数是否为素数
void Initialize(int n){ // 初始化用于素数判断的布尔数组,n代表本程序中需要埃氏筛判断的最大素数
    is_Prime = new(bool [n + 1]); // 为指针赋予数组空间
    is_Prime[0] = false;
    is_Prime[1] = false; // 0 和 1 不是素数
    for(int i = 2;i < n + 1;i += 1) is_Prime[i] = true; // 此处可使用cstring头文件下的memset函数填充
    for(int i = 2;i < n + 1;i += 1){
        if(is_Prime[i]){ // 素数的倍数必不是素数,合理运用该规律
            for(int j = 2;j * i < n + 1;j += 1){
                is_Prime[j * i] = false;
            }
        }
    }
}

Golang：

var Is_Prime []bool // 声明一个全局的布尔数组，用于判断下标对应数是否为素数
func Initialize (n int) { // 初始化素数判断数组，n为最大可判断素数
	// 为布尔数组申请空间
	Is_Prime = make([]bool,n + 1)
	for i := 2;i < n + 1;i += 1{
		Is_Prime[i] = true
	}
	// 0/1 不是素数
	Is_Prime[0] = false
	Is_Prime[1] = false
	for i := 2;i < n + 1;i += 1{
		// 素数的倍数必不是素数
		if Is_Prime[i]{
			for j := 2;j * i < n + 1;j += 1{
				Is_Prime[j * i] = false
			}
		}
	}
}

python:

Prime = [] # 定义一个列表，用于判断下标对应数是否为素数
def Initialize(n): # 初始化素数判断列表，n为最大可判断素数
    global Prime # 在初始化函数中更改素数判断列表
    # 0 和 1 不是素数
    Prime.append(False)
    Prime.append(False)
    for i in range(2,n + 1):
        Prime.append(True)
    # 素数的倍数必不是素数
    for i in range(2,n + 1):
        if Prime[i]:
            j = 2
            while i * j < n + 1:
                Prime[i * j] = False
                j += 1

Java：

public static boolean []Prime; // 声明一个布尔数组，使用下标来映射对应数，若为素数则下标对应数组值为真
    public static void Initialize(int n){
        Prime = new boolean[n + 1]; // 为布尔数组申请空间
        Prime[0] = Prime[1] = false; // 0 和 1 不是素数
        for(int i = 2;i < n + 1;i += 1){
            Prime[i] = true;
        }
        // 素数的倍数必不是素数
        for(int i = 2;i < n + 1;i += 1) {
            if (Prime[i]) {
                for (int j = 2; j * i < n + 1; j += 1) {
                    Prime[j * i] = false;
                }
            }
        }
    }