歐拉篩法，又稱篩法、線性篩法，是一種用來求解素數(shù)的方法。它的時間復雜度為O(n)。以下是C++語言的歐拉篩代碼實現(xiàn)： ```cpp #include #include 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; } ``` 現(xiàn)在假設(shè)需要判斷一個數(shù)M是否為素數(shù)： ```cpp bool isPrime(int M) { ??if (M < 2) { ????return false; // M不是素數(shù) ??} ??for (int i = 2; i * i <= M; ++i) { ????if (M % i == 0) { ??????return false; // M不是素數(shù) ????} ??} ??return true; // M是素數(shù) } ``` 注：以上代碼為獨立代碼，歐拉篩代碼和判斷素數(shù)代碼均可獨立使用。