Prime Number Algo

Sieve of Eratosthenes

【思路】:

埃式筛，寻找一定范围内质数的算法，主要思想是把质数的倍数当作合数一一屏蔽

【代码】:

• C++

  auto eratosthenes(int upperbound) {
    std::vector<bool> flag(upperbound + 1, true);
    flag[0] = flag[1] = false; //exclude 0 and 1
    for (int i = 2; i * i <= upperbound; ++i) {
      if (flag[i]) {
        for (int j = i * i; j <= upperbound; j += i)
          flag[j] = false;
      }
    }	
    return flag;
  }

• C++(自己写的)

  vector<bool> eratosthenes(int upperbound){
  	vector<bool> flag(upperbound + 1, true);
  	flag[0] = flag[1] = false;
  	for(int i = 2; i*i <= upperbound; ++i){
  		// if is prime num
  		if(flag[i]){
  			for(int j = i*i; j <= upperbound; j+=i){
  				flag[j] = false;
  			}
  		}
  	}
  	return flag;
  }