首页编写一个程序找出1000内的素数

编写一个程序找出1000内的素数

时间: 2025-01-01 07:34:55 浏览: 42

当然可以。在C++中，你可以使用一个简单的算法来找出1000以内的所有素数。这里我们将采用埃拉托斯特尼筛法（Sieve of Eratosthenes），这是一种有效地找到一定范围内所有素数的经典算法。 ```cpp #include <iostream> #include <vector> // 函数声明 std::vector<int> sieveOfEratosthenes(int n); int main() { int limit = 1000; std::vector<int> primes = sieveOfEratosthenes(limit); std::cout << "Prime numbers between 1 and " << limit << " are:\n"; for (int prime : primes) { std::cout << prime << " "; } std::cout << "\n"; return 0; } // 埃拉托斯特尼筛法 std::vector<int> sieveOfEratosthenes(int n) { std::vector<bool> isPrime(n+1, true); // 创建标记数组，初始全部设为真 isPrime[0] = isPrime[1] = false; // 0和1不是素数 for (int i = 2; i * i <= n; i++) { // 只需检查到√n if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; // 将i的倍数标记为非素数 } } } // 把结果收集到vector中 std::vector<int> primes; for (int i = 2; i <= n; i++) { if (isPrime[i]) primes.push_back(i); } return primes; } ``` 这段代码首先定义了一个`sieveOfEratosthenes`函数，用于执行埃拉托斯特尼筛选过程。然后，在`main`函数中调用该函数并打印出结果。运行这个程序后，你会看到1000以内的所有素数。

阅读全文