学步园

#include <iostream><br /> #include <cstdio><br /> #include <cstdlib><br /> #include <vector><br /> #include <map><br /> #include <set><br /> #include <queue><br /> #include <stack><br /> #include <algorithm><br /> #include <string><br /> #include <cstring><br /> #include <cmath></p> <p>using namespace std;</p> <p>const int MAX_NUM = 10000000;</p> <p>void PrimeFun1()<br /> {<br /> vector<int> prime;<br /> prime.reserve(MAX_NUM * 0.07);<br /> prime.push_back(2);</p> <p> for (int i=3; i <= MAX_NUM; i += 2)<br /> {<br /> bool isPrime = true;<br /> for (int j = 0; j < prime.size() && prime[j] * prime[j] <= i; j++)<br /> {<br /> if (i % prime[j] == 0)<br /> {<br /> isPrime=false;<br /> break;<br /> }<br /> }<br /> if (isPrime)<br /> {<br /> prime.push_back(i);<br /> }<br /> }<br /> cout << prime.size() << endl << MAX_NUM << endl << prime.size() / (double)MAX_NUM << endl;<br /> //for (int i = 0; i < prime.size(); i++)<br /> //{<br /> // cout << prime[i] << endl;<br /> //}<br /> }</p> <p>//better one<br /> bool isPrime[MAX_NUM+1];<br /> void PrimeFun2()<br /> {<br /> memset(isPrime,true,sizeof(isPrime));</p> <p> for(int i=4; i <= MAX_NUM; i+=2)<br /> isPrime[i]=false;</p> <p> for (int i = 3; i * i <= MAX_NUM; i += 2)<br /> {<br /> if (isPrime[i])<br /> {<br /> for (int j = i * i; j <= MAX_NUM; j += i)<br /> {<br /> isPrime[j] = false;<br /> }<br /> }<br /> }</p> <p> vector<int> prime;<br /> for (int i = 2;i <= MAX_NUM; i++)<br /> {<br /> if (isPrime[i])<br /> {<br /> prime.push_back(i);<br /> }<br /> }<br /> cout << prime.size() << endl << MAX_NUM << endl << prime.size() / (double)MAX_NUM << endl;<br /> //for (int i = 0; i < prime.size(); i++)<br /> //{<br /> // cout << prime[i] << endl;<br /> //}<br /> }</p> <p>int main()<br /> {<br /> PrimeFun2();<br /> PrimeFun1();<br /> system("pause");<br /> return 0;<br /> }