素数筛法

素数筛法

高效找出2-n之间的所有素数。

#include #include #include using namespace std;int n = 1000000;void PrimeSelect(vector &prime, vector &mark) { for (int i = 2; i <= n; i++) { if (mark[i] == true) { continue; } prime.push_back(i); if (i > sqrt(n)) { continue; } for (int j = i * i; j <= n; j += i) { mark[j] = true; } }}int main() { vector prime; vector mark(n + 1, false); PrimeSelect(prime, mark); for (int i = 0; i < prime.size(); i++) { cout << prime[i] << " "; } cout << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。