using namespace std;
const int MAX_NUM = 10000000;
void PrimeFun1()
{
vector<int> prime;
prime.reserve(MAX_NUM * 0.07);
prime.push_back(2);
for (int i=3; i <= MAX_NUM; i += 2)
{
bool isPrime = true;
for (int j = 0; j < prime.size() && prime[j] * prime[j] <= i; j++)
{
if (i % prime[j] == 0)
{
isPrime=false;
break;
}
}
if (isPrime)
{
prime.push_back(i);
}
}
cout << prime.size() << endl << MAX_NUM << endl << prime.size() / (double)MAX_NUM << endl;
//for (int i = 0; i < prime.size(); i++)
//{
// cout << prime[i] << endl;
//}
}
//better one
bool isPrime[MAX_NUM+1];
void PrimeFun2()
{
memset(isPrime,true,sizeof(isPrime));
for(int i=4; i <= MAX_NUM; i+=2)
isPrime[i]=false;
for (int i = 3; i * i <= MAX_NUM; i += 2)
{
if (isPrime[i])
{
for (int j = i * i; j <= MAX_NUM; j += i)
{
isPrime[j] = false;
}
}
}
vector<int> prime;
for (int i = 2;i <= MAX_NUM; i++)
{
if (isPrime[i])
{
prime.push_back(i);
}
}
cout << prime.size() << endl << MAX_NUM << endl << prime.size() / (double)MAX_NUM << endl;
//for (int i = 0; i < prime.size(); i++)
//{
// cout << prime[i] << endl;
//}
}
int main()
{
PrimeFun2();
PrimeFun1();
system("pause");
return 0;
}