题目描述

本题只让求质数个数，那么用总个数减去合数，就可以了，而合数必然是某一个数的倍数，用len记录就可以了

C++ 代码

#include<iostream>
using namespace std;
int st[1000005];
void inint(int n)
{
    int len=0;                          //记录合数
    for(int i=2;i<=n/2;i++)
        for(int j=2;i*j<=n;j++)
        {
            if(st[i*j]==0)              //只记录第一次出现的，防止重复记录
                len++;
            st[i*j]=1;                  //记为合数
        }
    cout<<n-1-len;
}
int main()
{
    int n;
    cin>>n;
    inint(n);
}