麻烦大家帮忙看一下求质数这段代码，求拍砖~ - 未名空间MITBBS历史存档

麻烦大家帮忙看一下求质数这段代码，求拍砖~# JobHunting - 待字闺中

l*t2015-08-22 07:08

1 楼

题目就是find all primes less or equal than n，要求体现OOD和写unit test。求拍
砖，多谢各位！
ps：不确定如果面试中让写C++ unit test，不用gtest, boost.test这些库，写成这样
可以吗？。。。因为之前自己写代码没有养成写unit test的习惯，感觉不太规范。。
#include
#include
#include
#include
#include
using namespace std;
class PrimeFinder {
friend class PrimeFinderTest;
public:
PrimeFinder(int n = 2) {
is_prime_.push_back(false);
is_prime_.push_back(false);
is_prime_.push_back(true);
primes_.push_back(2);
n_ = n;
}
vector get_primes(int n) {
if(n <= n_) {
return get_primes_subset(n);
} else {
extend_primes(n);
return primes_;
}
}
private:
vector is_prime_;
vector primes_;
int n_;
vector get_primes_subset(int n) {
auto iter = primes_.begin();
while(iter != primes_.end()) {
if(*iter <= n) ++iter;
else break;
}
return vector(primes_.begin(), iter);
}
void extend_primes(int n) {
is_prime_.reserve(n + 1);
is_prime_.insert(is_prime_.end(), n - n_, true);
int bound = sqrt(n);
for(int i = 2; i <= bound; ++i) {
if(is_prime_[i]) {
int j = i + i;
while(j <= n) {
if(j > n_) {
is_prime_[j] = false;
}
j += i;
}
}
}
for(int i = n_ + 1; i <= n; ++i) {
if(is_prime_[i]) primes_.push_back(i);
}
n_ = n;
}
};
template
string vec2str(const vector& vec) {
string str = "";
for(auto n : vec) {
str += to_string(n) + " ";
}
return str;
}
class PrimeFinderTest {
public:
void test_get_primes_subset(vector origin, int n) {
PrimeFinder test;
test.primes_ = origin;
vector subset = test.get_primes_subset(n);
cout << vec2str(subset) << endl;
}
void test_extend_primes(vector origin, vector origin_bool,
int n) {
PrimeFinder test;
test.primes_ = origin;
test.is_prime_ = origin_bool;
test.n_ = test.is_prime_.size() - 1;
test.extend_primes(n);
assert(test.n_ == n);
assert(test.is_prime_.size() == n + 1);
cout << vec2str(test.primes_) << endl;
}
void test_get_primes(int n) {
PrimeFinder test;
cout << vec2str(test.get_primes(n)) << endl;
}
void test_get_primes_suite(vector nums) {
PrimeFinder test;
for(int num : nums) {
cout << vec2str(test.get_primes(num)) << endl;
}
cout << endl;
}
};
int main() {
PrimeFinderTest test;
test.test_get_primes_subset(vector({2,3,5,7,11,13,17,19}),7);
test.test_get_primes_subset(vector({2,3,5,7,11,13,17,19}),8);
test.test_get_primes_subset(vector({2,3,5,7,11,13,17,19}),15);
test.test_extend_primes(vector({2,3,5,7}),
vector({false, false, true, true, false,
true, false, true, false}),
19);
test.test_get_primes(2);
test.test_get_primes(9);
test.test_get_primes(16);
test.test_get_primes(30);
test.test_get_primes_suite(vector({2, 9, 16, 30}));
test.test_get_primes_suite(vector({16, 9, 2, 30}));
test.test_get_primes_suite(vector({1,2,3,4,5}));
return 0;
}