朴素写法:

bool isprime(int x)
{
  if(x < 2) return 0;
  for(int i = 2; i <= x / i; i++)
    if(x % i == 0)
      return 0;
  return 1;
}

埃氏筛

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int n, cnt = 0;
bool a[100000005];

void sf(int x)
{
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= x; i++)
  {
    if(a[i] == 1)
    {
      cnt++;
      for(int j = i + i; j <= x; j += i)
      {
        a[j] = 0;
      }
    }
  }
}

int main()
{
  cin >> n;
  sf(n);
  cout << cnt << "\n";
  return 0;
}

欧拉线性筛

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int n, cnt = 0;
bool a[100000005];
int prime[10000005];

void sf(int x)
{
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= x; i++)
  {
    if(a[i] == 1)
      prime[cnt++] = i;
    for(int j = 0; j < cnt && i * prime[j] <= x;/*j是枚举prime数组, 被筛的数与prime[j]要小于等于总数*/ j++)
    {
       a[i * prime[j]] = 0;
       if(i % prime[j] == 0)/*筛完后将是prime[j]的倍数筛出*/
          break;
    }
  }
}

int main()
{
  cin >> n;
  sf(n);
  cout << cnt << "\n";
  return 0;
}