枸杞加水

1
bool numlist[100000];
2
//0代表质数，1代表非质数
3
int prime[100000], count;
4
void work(int n){
5
  for(int i=2; i<=n; i++){
6
    if(numlist[i]==0){  //如果是质数
7
      prime[++count] = i ;  //就先存入
8
      for(int j=i; i*j<=n; j++) numlist[i*j] = 1;  //然后将其平方后的所有倍数筛掉
9
    }
10
  }
11
  return;
12
}

1
bool numlist[100000];
2
//0代表质数，1代表非质数
3
int prime[100000], count;
4
void work(int n){
5
  for (int i = 2; i <= n; i++) {
6
    if (numlist[i]==0) ans[++count] = i;//是质数就先存入数组
7
    for (int j = 1; j <= count && i*prime[j] <= n; j++) {
8
      numlist[prime[j] * i] = 1; //每次让i乘已放入的质数，然后标记非质数
9
      if (i % prime[j] == 0) break;//但是如果i可以被该数整除就停止（关键）
10
    }
11
  }