在C++中如何利用面向对象编程思想来实现埃拉托斯特尼筛法,并以此找出小于200的所有素数?
时间: 2024-11-28 15:32:44 浏览: 28
埃拉托斯特尼筛法是一种古老而有效的算法,用于找出小于某一给定数的所有素数。结合C++的面向对象特性,我们可以设计一个类来封装筛法的实现细节,并将筛法作为一个对象的方法来调用。
参考资源链接:[C++面向对象程序设计:筛选法求素数](https://wenku.csdn.net/doc/5oxw67djeo?spm=1055.2569.3001.10343)
首先,让我们定义一个名为`Sieve`的类,该类将负责执行筛法并维护素数的状态。这个类可以包含一个布尔类型的数组,用来标记每个数是否为素数。以下是C++代码实现的示例:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
class Sieve {
private:
std::vector<bool> is_prime;
unsigned long n;
public:
Sieve(unsigned long limit) : n(limit), is_prime(limit + 1, true) {
is_prime[0] = false;
is_prime[1] = false;
}
void findPrimes() {
for (unsigned long p = 2; p <= sqrt(n); ++p) {
if (is_prime[p]) {
for (unsigned long i = p * p; i <= n; i += p) {
is_prime[i] = false;
}
}
}
}
void printPrimes() const {
for (unsigned long i = 2; i <= n; ++i) {
if (is_prime[i]) {
std::cout << i <<
参考资源链接:[C++面向对象程序设计:筛选法求素数](https://wenku.csdn.net/doc/5oxw67djeo?spm=1055.2569.3001.10343)
阅读全文