埃拉托斯特尼筛法

简介

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

主要思路

比如计算1,100之间的素数。主要思路是，从第一个质数2开始，数据里所有能被2整除的数字都不是质数，即从2开始，以2为步长，每跳经过的数字都能被2整除，把其标识为非质数。接着，从下一个质数3开始，重复上述过程。最终即可算出[1, 100]之间的所有素数

实现方法

Python

import numpy as np

a = np.arange(1, 101)
n_max = int(np.sqrt(len(a)))
is_prime = np.ones(len(a), dtype=bool)
is_prime[0] = False

for i in range(2, n_max):
    if i in a[is_prime]:
        is_prime[i**2-1::i] = False
        
print(a[is_prime])

C++

//埃拉托斯特尼筛法
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int prime_size, n_max;
    bool is_prime[1000000];
    cout << "Please input the range of prime number: ";
    cin >> prime_size;
    n_max = sqrt(prime_size) - 1;
    for (int i = 2; i <= prime_size; i++)
        is_prime[i] = true;
    for (int i = 2; i <= n_max; i++)
        if (is_prime[i])
            for (int j = i * i; j <= prime_size; j += i)
                is_prime[j] = false;
    for (int i = 2; i <= prime_size; i++)
        if (is_prime[i])
            cout << i << ' ';
    cout << endl;
    return 0;
}