stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<math.h>

using namespace std;

const int MAX = 1000000;

int prime(int n)

{

	int ans = 0;

	bool prime[MAX];

	memset(prime, 0, sizeof(prime));

	for (int i = 2; i < n;i++)  

	{ 

		for (int j = 2; j <= n / i; j++)

		{

			if (i*j <= n)

				prime[i*j] = 1;

		}

	}

	for (int i = 2; i <= n; i++)

	{

		if (!prime[i])

			ans++;

	}

	return ans;

}

int main()

{

	int n, m = 0;

	while (cin >> n&&m<30)

	{

		cout << prime(n) << endl;

		m++;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2749036002677143x):
#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    while (scanf ("%d",&n)!=EOF)

    {

    int prime[n+1],i,j;

    for (i=0;i<=n;i++)

        prime[i]=1;

    prime[0]=0;

    prime[1]=0;

    for (i=2;i<=sqrt(n);i++)

    {

        if (prime[i]==1)

        {

            for(j=2;i*j<=n;j++)

                prime[i*j]=0;

        }

    }

    int cnt=0;

    for (i=0;i<=n;i++)

    {

        if (prime[i]!=0)

            cnt++;

    }

    cout<<cnt<<endl;

    }

}
// Slower C++ solution:
#include<cstdio>

#include<string.h>

using namespace std;

int pNum;

bool IsPrime[1000010];

int Prime[1000010];

int GetPrime(int n){

    memset(IsPrime,true,sizeof(IsPrime));

    IsPrime[0]=IsPrime[1]=false;

    pNum=0;

    for(int i=2;i<=n;i++){

        if(IsPrime[i])Prime[++pNum]=i;

        for(int j=1;j<=pNum&&Prime[j]*i<=n;j++){

            IsPrime[Prime[j]*i]=false;

            if(i%Prime[j]==0)break;

        }

    }

    return pNum;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        printf("%d\n",GetPrime(n));

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4298161165248084x):
#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    while (scanf ("%d",&n)!=EOF)

    {

    int prime[n+1],i,j;

    for (i=0;i<=n;i++)

        prime[i]=1;

    prime[0]=0;

    prime[1]=0;

    for (i=2;i<=sqrt(n);i++)

    {

        if (prime[i]==1)

        {

            for(j=2;i*j<=n;j++)

                prime[i*j]=0;

        }

    }

    int cnt=0;

    for (i=0;i<=n;i++)

    {

        if (prime[i]!=0)

            cnt++;

    }

    cout<<cnt<<endl;

    }

}
// Slower C++ solution:
#include<stdio.h>

#include<math.h>

bool flag[1000000];

int main(void)

{

	long long i,j,p,n,count;

	p = (long long)sqrt(1000000.0);

	for(i = 3; i <= p; i = i + 2)

	{

		if(flag[i] == false)

		{

			for(j = i * i; j <= 1000000; j = j + 2 * i)

			{

				flag[j] = true;

				

			}

		}

	}

		

	while((scanf("%lld",&n)) != EOF)

	{

		

		if(n == 1 || n == 0)

			count = 0;

		else

		{

			count = 1;

			for(i = 3; i <= n; i = i + 2)

			{

				if(flag[i] == false)

					count++;

			}

		}

		printf("%lld\n",count);

	}

	



		

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.4721688238856516x):


#include<iostream>

#include<cstdio>



using namespace std;



const int maxn=1e6+5;



int isprime[maxn];



int solve(int n)

{

    int p=0;

    for(int i=2;i<=n;i++){

        if(!isprime[i]){

            p++;

        }

        for(int j=2*i;j<=n;j+=i){

            isprime[j]=1;

        }

    }

    return p;

}



int main()

{

    int n;

    while(~scanf("%d",&n)){

        cout<<solve(n)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define MAX 1000000

#define LMT 1000

unsigned flag[MAX>>6];

int primes[6000000];//5761455

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))

#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))



int sieve()

{

    unsigned i, j, k;

    for(i=3; i<LMT; i+=2)

        if(!ifc(i))

            for(j=i*i, k=i<<1; j<MAX; j+=k)

                isc(j);

    return 0;

}



int main()

{

    sieve();

    unsigned int i,L;

    int k=1, count;

    primes[0]=2;

    while(scanf("%d", &L)==1)

    {

        count=1;

        for( i=3; i<=L; i+=2)

        {

            if(ifc(i)==0)

                count++;

        }

        if(L>1)

            printf("%d\n", count);

        else printf("0\n");

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.3734692892121663x):


#include<iostream>

#include<cstdio>



using namespace std;



const int maxn=1e6+5;



int isprime[maxn];



int solve(int n)

{

    int p=0;

    for(int i=2;i<=n;i++){

        if(!isprime[i]){

            p++;

        }

        for(int j=2*i;j<=n;j+=i){

            isprime[j]=1;

        }

    }

    return p;

}



int main()

{

    int n;

    while(~scanf("%d",&n)){

        cout<<solve(n)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;



bool prime[1000000];



int main()

{

    int i,j,k,l,m,n;

    int count;

    while(cin>>n)

    {

        memset(prime,0,sizeof(prime));

        prime[1]=1;

        prime[2]=0;



        count=0;



        for(j=2;j*j<=n;j++)

        {

            if(prime[j]==0)

            {

                for(k=2;k*j<=n;k++)

                {

                   prime[j*k]=1;

                }

            }

        }

        for(i=1;i<=n;i++)

        {

            if(prime[i]==0)

            count++;

        }

        cout << count << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.261426835910122x):


#include<iostream>

#include<cstdio>



using namespace std;



const int maxn=1e6+5;



int isprime[maxn];



int solve(int n)

{

    int p=0;

    for(int i=2;i<=n;i++){

        if(!isprime[i]){

            p++;

        }

        for(int j=2*i;j<=n;j+=i){

            isprime[j]=1;

        }

    }

    return p;

}



int main()

{

    int n;

    while(~scanf("%d",&n)){

        cout<<solve(n)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<math.h>

using namespace std;

const int MAX = 1000000;

int prime(int n)

{

	int ans = 0;

	bool prime[MAX];

	memset(prime, 0, sizeof(prime));

	for (int i = 2; i < n;i++)  

	{ 

		for (int j = 2; j <= n / i; j++)

		{

			if (i*j <= n)

				prime[i*j] = 1;

		}

	}

	for (int i = 2; i <= n; i++)

	{

		if (!prime[i])

			ans++;

	}

	return ans;

}

int main()

{

	int n, m = 0;

	while (cin >> n&&m<30)

	{

		cout << prime(n) << endl;

		m++;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2762333868820814x):


#include<iostream>

#include<cstdio>



using namespace std;



const int maxn=1e6+5;



int isprime[maxn];



int solve(int n)

{

    int p=0;

    for(int i=2;i<=n;i++){

        if(!isprime[i]){

            p++;

        }

        for(int j=2*i;j<=n;j+=i){

            isprime[j]=1;

        }

    }

    return p;

}



int main()

{

    int n;

    while(~scanf("%d",&n)){

        cout<<solve(n)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<string.h>

using namespace std;

int pNum;

bool IsPrime[1000010];

int Prime[1000010];

int GetPrime(int n){

    memset(IsPrime,true,sizeof(IsPrime));

    IsPrime[0]=IsPrime[1]=false;

    pNum=0;

    for(int i=2;i<=n;i++){

        if(IsPrime[i])Prime[++pNum]=i;

        for(int j=1;j<=pNum&&Prime[j]*i<=n;j++){

            IsPrime[Prime[j]*i]=false;

            if(i%Prime[j]==0)break;

        }

    }

    return pNum;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        printf("%d\n",GetPrime(n));

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4306519103283513x):


#include<iostream>

#include<cstdio>



using namespace std;



const int maxn=1e6+5;



int isprime[maxn];



int solve(int n)

{

    int p=0;

    for(int i=2;i<=n;i++){

        if(!isprime[i]){

            p++;

        }

        for(int j=2*i;j<=n;j+=i){

            isprime[j]=1;

        }

    }

    return p;

}



int main()

{

    int n;

    while(~scanf("%d",&n)){

        cout<<solve(n)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<math.h>

bool flag[1000000];

int main(void)

{

	long long i,j,p,n,count;

	p = (long long)sqrt(1000000.0);

	for(i = 3; i <= p; i = i + 2)

	{

		if(flag[i] == false)

		{

			for(j = i * i; j <= 1000000; j = j + 2 * i)

			{

				flag[j] = true;

				

			}

		}

	}

		

	while((scanf("%lld",&n)) != EOF)

	{

		

		if(n == 1 || n == 0)

			count = 0;

		else

		{

			count = 1;

			for(i = 3; i <= n; i = i + 2)

			{

				if(flag[i] == false)

					count++;

			}

		}

		printf("%lld\n",count);

	}

	



		

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.4661927945532454x):
#include<iostream>

#include<cstring> 

using namespace std;

bool a[10000000];

int main()

{

	int n;

	while(cin>>n)

	{	

		int js=0;

		for (int i=2;i<=n;i++)

		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}

		cout<<js<<endl;   

	}

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define MAX 1000000

#define LMT 1000

unsigned flag[MAX>>6];

int primes[6000000];//5761455

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))

#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))



int sieve()

{

    unsigned i, j, k;

    for(i=3; i<LMT; i+=2)

        if(!ifc(i))

            for(j=i*i, k=i<<1; j<MAX; j+=k)

                isc(j);

    return 0;

}



int main()

{

    sieve();

    unsigned int i,L;

    int k=1, count;

    primes[0]=2;

    while(scanf("%d", &L)==1)

    {

        count=1;

        for( i=3; i<=L; i+=2)

        {

            if(ifc(i)==0)

                count++;

        }

        if(L>1)

            printf("%d\n", count);

        else printf("0\n");

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.3693842568271273x):
#include<iostream>

#include<cstring> 

using namespace std;

bool a[10000000];

int main()

{

	int n;

	while(cin>>n)

	{	

		int js=0;

		for (int i=2;i<=n;i++)

		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}

		cout<<js<<endl;   

	}

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;



bool prime[1000000];



int main()

{

    int i,j,k,l,m,n;

    int count;

    while(cin>>n)

    {

        memset(prime,0,sizeof(prime));

        prime[1]=1;

        prime[2]=0;



        count=0;



        for(j=2;j*j<=n;j++)

        {

            if(prime[j]==0)

            {

                for(k=2;k*j<=n;k++)

                {

                   prime[j*k]=1;

                }

            }

        }

        for(i=1;i<=n;i++)

        {

            if(prime[i]==0)

            count++;

        }

        cout << count << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2575346423590705x):
#include<iostream>

#include<cstring> 

using namespace std;

bool a[10000000];

int main()

{

	int n;

	while(cin>>n)

	{	

		int js=0;

		for (int i=2;i<=n;i++)

		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}

		cout<<js<<endl;   

	}

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<math.h>

using namespace std;

const int MAX = 1000000;

int prime(int n)

{

	int ans = 0;

	bool prime[MAX];

	memset(prime, 0, sizeof(prime));

	for (int i = 2; i < n;i++)  

	{ 

		for (int j = 2; j <= n / i; j++)

		{

			if (i*j <= n)

				prime[i*j] = 1;

		}

	}

	for (int i = 2; i <= n; i++)

	{

		if (!prime[i])

			ans++;

	}

	return ans;

}

int main()

{

	int n, m = 0;

	while (cin >> n&&m<30)

	{

		cout << prime(n) << endl;

		m++;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2723157094368394x):
#include<iostream>

#include<cstring> 

using namespace std;

bool a[10000000];

int main()

{

	int n;

	while(cin>>n)

	{	

		int js=0;

		for (int i=2;i<=n;i++)

		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}

		cout<<js<<endl;   

	}

}
// Slower C++ solution:
#include<cstdio>

#include<string.h>

using namespace std;

int pNum;

bool IsPrime[1000010];

int Prime[1000010];

int GetPrime(int n){

    memset(IsPrime,true,sizeof(IsPrime));

    IsPrime[0]=IsPrime[1]=false;

    pNum=0;

    for(int i=2;i<=n;i++){

        if(IsPrime[i])Prime[++pNum]=i;

        for(int j=1;j<=pNum&&Prime[j]*i<=n;j++){

            IsPrime[Prime[j]*i]=false;

            if(i%Prime[j]==0)break;

        }

    }

    return pNum;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        printf("%d\n",GetPrime(n));

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4281895825400908x):
#include<iostream>

#include<cstring> 

using namespace std;

bool a[10000000];

int main()

{

	int n;

	while(cin>>n)

	{	

		int js=0;

		for (int i=2;i<=n;i++)

		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}

		cout<<js<<endl;   

	}

}
// Slower C++ solution:
#include<stdio.h>

#include<math.h>

bool flag[1000000];

int main(void)

{

	long long i,j,p,n,count;

	p = (long long)sqrt(1000000.0);

	for(i = 3; i <= p; i = i + 2)

	{

		if(flag[i] == false)

		{

			for(j = i * i; j <= 1000000; j = j + 2 * i)

			{

				flag[j] = true;

				

			}

		}

	}

		

	while((scanf("%lld",&n)) != EOF)

	{

		

		if(n == 1 || n == 0)

			count = 0;

		else

		{

			count = 1;

			for(i = 3; i <= n; i = i + 2)

			{

				if(flag[i] == false)

					count++;

			}

		}

		printf("%lld\n",count);

	}

	



		

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.468045023057825x):
#include <iostream>

using namespace std;

#define MAX_N 999999



int prime[MAX_N];

bool is_prime[MAX_N];



int sieve(int n)

{

	int p = 0;

	for(int i = 0; i<=n; i++)

		is_prime[i] = true;

	

	is_prime[0] = is_prime[1] = false;

	

	for(int i=2; i<=n; i++)

	{

		if(is_prime[i])

		{

			prime[p++] = i;

			for(int j = 2*i; j<=n; j+=i)

				is_prime[j] = false;

		}

	}

	return p;

}



int main()

{

	int s;

	while( cin >> s )

	{

		cout << sieve(s) << endl;

	}

	

		

	return 0;	

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define MAX 1000000

#define LMT 1000

unsigned flag[MAX>>6];

int primes[6000000];//5761455

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))

#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))



int sieve()

{

    unsigned i, j, k;

    for(i=3; i<LMT; i+=2)

        if(!ifc(i))

            for(j=i*i, k=i<<1; j<MAX; j+=k)

                isc(j);

    return 0;

}



int main()

{

    sieve();

    unsigned int i,L;

    int k=1, count;

    primes[0]=2;

    while(scanf("%d", &L)==1)

    {

        count=1;

        for( i=3; i<=L; i+=2)

        {

            if(ifc(i)==0)

                count++;

        }

        if(L>1)

            printf("%d\n", count);

        else printf("0\n");

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.3706503840505446x):
#include <iostream>

using namespace std;

#define MAX_N 999999



int prime[MAX_N];

bool is_prime[MAX_N];



int sieve(int n)

{

	int p = 0;

	for(int i = 0; i<=n; i++)

		is_prime[i] = true;

	

	is_prime[0] = is_prime[1] = false;

	

	for(int i=2; i<=n; i++)

	{

		if(is_prime[i])

		{

			prime[p++] = i;

			for(int j = 2*i; j<=n; j+=i)

				is_prime[j] = false;

		}

	}

	return p;

}



int main()

{

	int s;

	while( cin >> s )

	{

		cout << sieve(s) << endl;

	}

	

		

	return 0;	

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;



bool prime[1000000];



int main()

{

    int i,j,k,l,m,n;

    int count;

    while(cin>>n)

    {

        memset(prime,0,sizeof(prime));

        prime[1]=1;

        prime[2]=0;



        count=0;



        for(j=2;j*j<=n;j++)

        {

            if(prime[j]==0)

            {

                for(k=2;k*j<=n;k++)

                {

                   prime[j*k]=1;

                }

            }

        }

        for(i=1;i<=n;i++)

        {

            if(prime[i]==0)

            count++;

        }

        cout << count << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.258741000534307x):
#include <iostream>

using namespace std;

#define MAX_N 999999



int prime[MAX_N];

bool is_prime[MAX_N];



int sieve(int n)

{

	int p = 0;

	for(int i = 0; i<=n; i++)

		is_prime[i] = true;

	

	is_prime[0] = is_prime[1] = false;

	

	for(int i=2; i<=n; i++)

	{

		if(is_prime[i])

		{

			prime[p++] = i;

			for(int j = 2*i; j<=n; j+=i)

				is_prime[j] = false;

		}

	}

	return p;

}



int main()

{

	int s;

	while( cin >> s )

	{

		cout << sieve(s) << endl;

	}

	

		

	return 0;	

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<math.h>

using namespace std;

const int MAX = 1000000;

int prime(int n)

{

	int ans = 0;

	bool prime[MAX];

	memset(prime, 0, sizeof(prime));

	for (int i = 2; i < n;i++)  

	{ 

		for (int j = 2; j <= n / i; j++)

		{

			if (i*j <= n)

				prime[i*j] = 1;

		}

	}

	for (int i = 2; i <= n; i++)

	{

		if (!prime[i])

			ans++;

	}

	return ans;

}

int main()

{

	int n, m = 0;

	while (cin >> n&&m<30)

	{

		cout << prime(n) << endl;

		m++;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.273529966166885x):
#include <iostream>

using namespace std;

#define MAX_N 999999



int prime[MAX_N];

bool is_prime[MAX_N];



int sieve(int n)

{

	int p = 0;

	for(int i = 0; i<=n; i++)

		is_prime[i] = true;

	

	is_prime[0] = is_prime[1] = false;

	

	for(int i=2; i<=n; i++)

	{

		if(is_prime[i])

		{

			prime[p++] = i;

			for(int j = 2*i; j<=n; j+=i)

				is_prime[j] = false;

		}

	}

	return p;

}



int main()

{

	int s;

	while( cin >> s )

	{

		cout << sieve(s) << endl;

	}

	

		

	return 0;	

}
// Slower C++ solution:
#include<cstdio>

#include<string.h>

using namespace std;

int pNum;

bool IsPrime[1000010];

int Prime[1000010];

int GetPrime(int n){

    memset(IsPrime,true,sizeof(IsPrime));

    IsPrime[0]=IsPrime[1]=false;

    pNum=0;

    for(int i=2;i<=n;i++){

        if(IsPrime[i])Prime[++pNum]=i;

        for(int j=1;j<=pNum&&Prime[j]*i<=n;j++){

            IsPrime[Prime[j]*i]=false;

            if(i%Prime[j]==0)break;

        }

    }

    return pNum;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        printf("%d\n",GetPrime(n));

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.428952763820394x):
#include <iostream>

using namespace std;

#define MAX_N 999999



int prime[MAX_N];

bool is_prime[MAX_N];



int sieve(int n)

{

	int p = 0;

	for(int i = 0; i<=n; i++)

		is_prime[i] = true;

	

	is_prime[0] = is_prime[1] = false;

	

	for(int i=2; i<=n; i++)

	{

		if(is_prime[i])

		{

			prime[p++] = i;

			for(int j = 2*i; j<=n; j+=i)

				is_prime[j] = false;

		}

	}

	return p;

}



int main()

{

	int s;

	while( cin >> s )

	{

		cout << sieve(s) << endl;

	}

	

		

	return 0;	

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main(){

	int n, cnt;

	

	while(cin >> n){

		bool prime[1000000] = {false};

		prime[1] = true; //1???????????\

		

		// ??¨??????????????????????????????

		for(int j = 2; j*j <= n; j++){

			if(prime[j] == false){

				for(int k = j; k*j <= n; k++){

					prime[j*k] =true;

				}

			}

		}

		cnt = 0;

		for(int i = 1; i <= n; i++){

			if(prime[i] == false) cnt++;

		}

		

		cout << cnt << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 2.256688509296628x):
#include<iostream>

using namespace std;

int main(){

	int n, cnt;	



	while(cin >> n){

		bool prime[n+1] = {false};

		prime[1] = true;

		

		// ??¨??????????????????????????????

		for(int j = 2; j*j <= n; j++){

			if(prime[j] == false){

				for(int k = j; k*j <= n; k++){

					prime[j*k] = true;

				}

			}

		}

		cnt = 0;

		for(int i = 1; i <= n; i++){

			if(prime[i] == false) cnt++;

		}

		

		cout << cnt << endl;

	}

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main(){

	int n, cnt;

	

	while(cin >> n){

		bool prime[1000000] = {false};

		prime[1] = true; //1???????????\

		

		// ??¨??????????????????????????????

		for(int j = 2; j*j <= n; j++){

			if(prime[j] == false){

				for(int k = j; k*j <= n; k++){

					prime[j*k] =true;

				}

			}

		}

		cnt = 0;

		for(int i = 1; i <= n; i++){

			if(prime[i] == false) cnt++;

		}

		

		cout << cnt << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 2.256688509296628x):
#include<iostream>

using namespace std;

int main(){

	int n, cnt;		

	while(cin >> n){

		//??????????????????1???????????\??±??????

		bool prime[n+1] = {false};

		prime[1] = true;

		// ??¨??????????????????????????????

		for(int j = 2; j*j <= n; j++){

			if(!prime[j]){

				for(int k = j; k*j <= n; k++){

					prime[j*k] = true;

				}

			}

		}

		cnt = 0;

		//false?????¨????´???°

		for(int i = 1; i <= n; i++){

			if(!prime[i]) cnt++;

		}

		cout << cnt << endl;

	}

}
// Slower C++ solution:
#include <cstdio>



using namespace std;



int main() {

    long NUM = 1000000;

    long n;

	long counter = 0;

	bool primeNum[NUM + 10];



	long i, ii, j, len = NUM + 10;

	

	primeNum[0] = primeNum[1] = false;

	for (i = 2; i < len; i++) primeNum[i] = true;

	

	ii = 4;

    for(i = 2; ii < NUM;) {

        if (primeNum[i]) {

            for (j = ii; j < NUM; j += i) {

                primeNum[j] = false;

            }

        }

        

        i++;

        ii = i * i;

    }

    

    while (scanf("%ld", &n) != EOF) {

        counter = 0;

        

        for (i = 0; i <= n; i++) {

            if (primeNum[i]) counter++;

        }

        

        printf("%ld\n", counter);

    }



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.349987603370263x):
#include <bits/stdc++.h>

 

using namespace std;



static const long MAX = 1000000L;

 

int main() {

    vector<long> prime;

    vector<long> dp;

    bool isPrime;

    long n, m;

 

    long i, len = sqrt(MAX) + 1;

    long j, lenJ;

    long k;

     

    prime.push_back(2);

    dp.push_back(0);

	dp.push_back(0);

	dp.push_back(1);



    for (i = 3; i <= len; i += 2) {

        isPrime = true;

        lenJ = prime.size();

        k = sqrt(i) + 1;

        for (j = 0; j < lenJ; j++) {

            if (k <= prime[j]) break;



            if (i % prime[j] == 0) {

                isPrime = false;



                break;

            }

	}



        if (isPrime) prime.push_back(i);

    }



    lenJ = prime.size();

     

    while (cin >> n) {

	if (n < dp.size()) {

		cout << dp[n] << endl;



		continue;

	}

         

	m = dp.size();

        for (i = m; i <= n; i += 2) {

            isPrime = true;



            k = sqrt(i) + 1;

            for (j = 0; j < lenJ; j++) {

                if (k <= prime[j]) break;



                if (i % prime[j] == 0) {

                    isPrime = false;



                    break;

                }

            }



            if (isPrime) {

		dp.push_back(dp.back() + 1);

		dp.push_back(dp.back());

	    } else {

		dp.push_back(dp.back());

		dp.push_back(dp.back());

	    }

        }

         

        cout << dp[n] << endl;

    }

 

    return 0;

}