如何编程求解 100 以内的质数？
关注者
1,240被浏览
312,756登录后你可以
不限量看优质回答私信答主深度交流精彩内容一键收藏
我尝试用一行C++11代码模仿
@大人的 Python式实现：
copy_if(range(2, 101), ostream_iterator<int>(cout, " "), [](int x){ return none_of(range(2, x), [x](int y) { return x % y == 0; }); });
这样比较容易理解：
copy_if( // 复制
range(2, 101), // 数列 { 2, 3, .. 100 } 中的整数
ostream_iterator<int>(cout, " "), // 至cout（每个输出后加入空格）
[](int x) { // 仅当对于每个整数x
return none_of( // 没有一个
range(2, x), // y in { 2, ..., x - 1 }
[x](int y) { // 乎合
return x % y == 0; // y 为 x 的因子
}
);
}
);
-----
为了实现这个函数式实现，C++11不提供range()的功能，需要自行实现一个。完整的程序是这样的：
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
template <typename T>
class range_type {
public:
class range_iterator {
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category;
range_iterator(T v) : v_(v) {}
T operator*() const { return v_; }
range_iterator operator++() { ++v_; return *this; }
range_iterator operator++(int) { range_iterator copy(*this); ++v_; return copy; }
bool operator==(const range_iterator &other) const { return v_ == other.v_; }
bool operator!=(const range_iterator &other) const { return v_ != other.v_; }
private:
T v_;
};
range_type(T lower, T upper) : lower_(lower), upper_(upper) {}
range_iterator begin() const { return range_iterator(lower_); }
range_iterator end() const { return range_iterator(upper_); }
private:
T lower_, upper_;
};
template <typename T>
range_type<T> range(T lower, T upper) { return range_type<T>(lower, upper); }
template <typename Container, typename UnaryPredicate>
bool none_of(const Container& c, UnaryPredicate pred) { return none_of(c.begin(), c.end(), pred); }
template <typename Container, typename DestIterator, typename UnaryPredicate>
void copy_if(const Container& c, DestIterator d, UnaryPredicate pred) { copy_if(c.begin(), c.end(), d, pred); }
int main() {
copy_if(range(2, 101), ostream_iterator<int>(cout, " "), [](int x){ return none_of(range(2, x), [x](int y) { return x % y == 0; }); });
return 0;
}
另外，因为C++ algorithm标头档的函数都使用 begin, end 作为参数，为了把程序写成一行，我加入了使用container作为参数的none_of()和copy_if()。
相信没有学生会把这段代码当功课交吧。
-----
2014/11/10更新：不少评论说了各种「优化」方法。
包括把内循环的范围从[2, x)降至[2, \left \lfloor \frac{x}{2} \right \rfloor + 1)，或者更好的[2, \left \lfloor \sqrt{x} \right \rfloor + 1)。另外也可以只测试之前的质数是否因子。
我作了一个简单的测试：
void test(int t, std::vector<int>& p, int n, function<bool(int)> isPrime) {
p.clear();
clock_t start = clock();
copy_if(range(2, n + 1), back_inserter(p), isPrime);
clock_t end = clock();
cout << t << ". " << p.size() << " " << (end - start) * 1000.0 / CLOCKS_PER_SEC << "ms" << endl;
}
int main() {
std::vector<int> p;
p.reserve(10000);
const int n = 100000;
test(1, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return x % y == 0; }); });
test(2, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y * 2 <= x && x % y == 0; }); });
test(3, p, n, [](int x) { return none_of(range(2, x / 2 + 1), [x](int y) { return x % y == 0; }); });
test(4, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y * y <= x && x % y == 0; }); });
test(5, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y <= (int)sqrt(x) && x % y == 0; }); });
test(6, p, n, [](int x) { return none_of(range(2, (int)sqrt(x) + 1), [x](int y) { return x % y == 0; }); });
test(7, p, n, [&p](int x) { return none_of(p, [x](int y) { return x % y == 0; }); });
test(8, p, n, [&p](int x) { return none_of(p, [x](int y) { return y * y <= x && x % y == 0; }); });
test(9, p, n, [&p](int x) { return none_of(p, [x](int y) { return y <= (int)sqrt(x) && x % y == 0; }); });
test(10, p, n, [&p](int x) {
for (auto y : p) {
if (y > (int)sqrt(x))
return true;
else if (x % y == 0)
return false;
}
return true;
});
//copy(p, ostream_iterator<int>(cout, " "));
return 0;
}
为了测试性能，我把n调至100000，并避免输出字符串的开销，只把结果写在vector里。
运行结果：
1. 9592 1564ms
2. 9592 927ms
3. 9592 784ms
4. 9592 569ms
5. 9592 293ms
6. 9592 11ms
7. 9592 159ms
8. 9592 65ms
9. 9592 33ms
10. 9592 4ms如果能减少范围，直接改动上界（测试3、6）是较好的。虽然测试5减少了调用sqrt()，但因为仍然需要迭代整个范围，会比测试6要慢得多。
对于使用之前结果中的质数，测试7比测试6（简单的开方优化）要慢。但在这情况下，我们不能改变上界（不知道现时已存的质数哪个大于x的开方），测试8和9的结果仍然比测试6要慢。
最后，唯有放弃使用none_of()，才能避免迭代整个范围，达到这些测试中最优的测试10。