test2

欧拉筛法，又称筛法、线性筛法，是一种用来求解素数的方法。它的时间复杂度为O(n)。以下是C++语言的欧拉筛代码实现： ```cpp #include <<\iostream>> #include <<\vector>> using namespace std; vector is_prime; vector primes; void sieve(int n) {   is_prime.resize(n + 1, true);   is_prime[0] = is_prime[1] = false;   for (int i = 2; i <= n; ++i) {     if (is_prime[i]) {       primes.push_back(i);     }     for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {       is_prime[i * primes[j]] = false;       if (i % primes[j] == 0) {         break;       }     }   } } int main() {   int n;   cin >> n;   sieve(n);   for (int i = 0; i < primes.size(); ++i) {     cout << primes[i] << " ";   }   cout << endl;   return 0; } ``` 现在假设需要判断一个数M是否为素数： ```cpp bool isPrime(int M) {   if (M < 2) {     return false; // M不是素数   }   for (int i = 2; i * i <= M; ++i) {     if (M % i == 0) {       return false; // M不是素数     }   }   return true; // M是素数 } ``` 注：以上代码为独立代码，欧拉筛代码和判断素数代码均可独立使用。