#include<bits/stdc++.h>
using namespace std;
int n,ind=1,ans=1,xb;
bool Isprime[100005];
int primes[100005];
void res()
{
    memset(Isprime,1,sizeof Isprime);
    for (int i=2;i<=100005;i++)
    {
        if (Isprime[i]) primes[++xb]=i;
        for (int j=2;j*i<=100005;j++) Isprime[j*i]=0;
    }
}
int main()
{
    cin>>n;
    res();
    while(primes[ind]<=n)
    {
        ans++;ind++;
    }
    cout<<ans;
}

AC code 用的是埃氏筛选

用埃式筛选或线性筛选

用埃式筛选或线性筛选

用埃式筛选或线性筛选

我只会这样

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int check(int a,int b)
{
    for(int i=2;i<max(a,b);i++)
        if(a%i==0&&b%i==0)
            return 0;
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cnt+=check(i,n);
    cout<<cnt;
    return 0;
}

这是高级班的题，好像要用埃式筛选还是线性筛选

有没有高级班的大佬看一下

我这个也不行

#include<bits/stdc++.h>
using namespace  std;
int n,shu[100001],ans=1; 
int  main( ) 
{
    cin>>n;
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    for (int i=2;i<=n;i++)
    {
        int x=i, cnt=0;
        for (int j=1;j<=x;j++)
        {
            if (x%j==0)
                cnt++;
        }
        if (cnt==2)
            ans++;
    }
    cout<<ans;
    return 0;   
}