线性筛质数模版（Python/C++）

C++

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
 
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

Python 

 
def check(num) :
    flag = [True] * (num + 1)
    prime = []
    for i in range(2,num+1) :
        if flag[i] : 
            prime.append(i)
        j = 0 
        while prime[j] <= num // i :
            flag[prime[j] * i] = False
            if i % prime[j] == 0 : break
            j += 1
            
    return prime