一个伪O（1）时间的算法QWQ。
其实就是欧拉线性筛法。

#include <bits/stdc++.h>
#define maxn 2000000000
using namespace std;
bool p[maxn];
int a[maxn/5],cnt=0;
int main () {
    p[0]=1;
    p[1]=1;
    int n,sum=0;
    scanf("%d",&n);
    
    for (int i=2;i<=n;i++) {
        if (p[i]==0) a[cnt++]=i;
        for (int j=0;j<cnt;j++) {
            if (i*a[j]>n) break;
            p[i*a[j]]=1;
            if (i%a[j]==0) break;
        }
    }
    
    for (int i=0;i<=n;i++) if(!p[i]) sum++;
    cout<<sum;
}

#include<iostream>
using namespace std;

bool sushu(int n);

int main()
{
    int n;cin>>n;
    int cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(sushu(i)==1)
            cnt++;
    }
    cout<<cnt;
    return 0;
}

bool sushu(int n)
{
    if(n==2) return 1;
    if(n==1) return 0;  
    for(int i=2;i<n;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}

#include<iostream>
#define Yes 1
#define No -1
using namespace std;

int is_prime(int x)
{
    if(x==1)
        return No;
    if(x==2)
        return Yes;
    for(int i=2;i<x;i++)
    {
        if(x%i==0)
            return No;
    }
    return Yes;
}

int main()
{
    int flag=0;
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
    {
        if(is_prime(i)==Yes)
            flag++;
    }
    cout<<flag<<endl;

    system("pause");
    return 0;
}

#include<stdio.h>
int main()
{
int a=0,i=0,n=0,num=0;
scanf("%d",&n);
a=2;
while(a<=n)
{
for(i=2;i<n;i++)
if(a%i==0) break;
if(a==i) num++;
a++;
}
printf("%d",num);
return 0;
}

#include <iostream>
using namespace std;
int main()
{
int a,b=2,c=2,d=0;
cin>>a;

while(b<=a)
{
while(c<=b-1)
{
if(b%c==0)
break;
c++;
}
if(c==b)
d++;
c=2;
b++ ;

}
cout<<d;

return 0;
}