这道题我们可以使用贪心的思想来解决。

首先将所有区间按照右端点从小到大排序，然后从前往后遍历每个区间。对于第 i 个区间，选取左端点最靠右且与前面的区间不重合的区间作为下一个被选择的区间。

具体实现时，需要记录当前已经选择的区间的右端点 r 和可选区间的起点 start，然后遍历每个区间：

• 如果当前区间的起点 l>r，说明该区间与之前的区间不重合，可以被选择。更新 r=end，start 不变。
• 如果当前区间的起点 l≤r，说明该区间和之前的区间重合，不能被选择。此时直接跳过即可。

最终选择的所有区间即为最多不重叠子区间。

#include<iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;

    // 初始化为 true
    vector<bool> is_prime(n+1, true);
    int cnt = 0;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            ++cnt;
            for (int j = i*i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,sum=0;
    cin>>n;
    for (int i=2;i<=n;i++)
    {
        int x=1;
        for (int j=2;j<i;j++)
        {
            if (i%j==0)
            {
                x=0;
                break;
            }
        }
        if (x==1)
        {
            sum++;
        }
    }
    cout<<sum;~~~~****~~~~
    return 0;
}```*第一层循环遍历每个数，第二层算有没有因数。*```
先别走，点个赞吧！

#include <iostream>
using namespace std;
int main()
{
    int n;
    int sum = 0;
    cin >> n;
    for(int i =2;i<=n;i++)
    {
        int flag = 1;
        for(int j =2;j<=i-1;j++)
        {

            if(i%j==0)
            {   flag = 0;
                break;
            }
        }
        if (flag ==1)
        {   sum += 1;
            
        }
            
    }
    cout << sum;
    return 0;
}

#include <iostream>
using namespace std;
bool prime(int n)
{
    if(n == 1)
    {
        return 0;
    }
    for(int i = 2;i < n;i++)
    {
        if(n % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n , sum = 0;
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        if(prime(i))
        {
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

哒哒~~~埃氏筛法！

#include<bits/stdc++.h>
using namespace std;
int n,sum;
bool is_prime[100001];
int main()
{
    cin>>n;
    for (int i=2;i<=n;i++)
    {
        if (!is_prime[i])
        {
            sum++;
            for (int j=2*i;j<=n;j+=i)
            {
                is_prime[j]=1;
            }
        }
    }
    cout<<sum;
    return 0;
} 

题解里有贪心，有枚举，有筛法 , 就写个函数吧👀️ (yasuo)

1.写一个函数sus()用来造质数

2,for语句遍历2-n

(1肯定不是,也方便我们在函数中判断,所以不写1-n)

3.sus()判断i是否为质数

4.打印

#include <iostream>
bool sus(int a){
for(int i=2;i*i<=a;i++) if(a%i==0) return false;
return true;}
int main(){
int q,sum=0;std::cin>>q;
for(int i=2;i<=q;i++) if(sus(i)) sum++;
std::cout<<sum;return 0;}

看到题解里有用贪心算法解这题的，那我提供一种用枚举的吧

在获取到n以后，通过for循环枚举出2~n之间的所有数字（注意：因为1不是质数，所以这里没有把1算进去，并且这样不用专门处理输入为1的情况）

接下来再用一个for循环，枚举出2~i-1之间所有的数（因为1和i肯定可以被i整除，所以只要2到i-1之间有一个可以被i整除，那么i就不是质数），通过记数变量cnt统计2到i-1之间有多少个数可以被i整除

如果cnt == 0的话，就将用于统计质数个数的变量sum+=1

最后输出sum，完工！

#include <iostream>
using namespace std;

int main()
{
    int n,sum = 0;
    cin >> n;
    for(int i = 2;i <= n;i++)
    {
        int cnt = 0;
        for(int j = 2;j <= i - 1;j++)
        {
            if(i % j == 0)
                cnt++;
        }
        if (cnt == 0)
            sum += 1;
    }
    cout << sum;
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
    short n,z=0,sum=0;//分别为输入的数字、质数状态和质数的总量
    cin>>n;
    for (int i=3;i<=n;i++)
    {
        z=0;
        if (i==1 || i==2)
            continue;
        for (int c=3;c<=i-1;c++)
        {
            if (i%c==0)
            {
                z=1;
                break;
            }    
            else
                z=0;
        }
        if (z==0)
            sum+=1;
    }
    cout<<sum;
}//代码有点长，尽量看完，看完后不要复制，用自己的方法或我的方法再做一次

题解里有贪心，有枚举，就写个筛法吧（doge）

1 创建存储2-n的一个数组

2 遍历数组，找出倍数，sum++

3 输出sum

效果：（n=6）2 3 4 5 6 （i=2时） 2 3 0 5 0 （i=3） 2 3 0 5 0 （a[4]=0,所以i跳至5） 2 3 0 5 0

#include<iostream>
using namespace std;
int main()
{
    int a[1005]={0},n,sum=0,k=2;
    cin>>n;
    
    for (;k<=n;k++)///集合中'['或']'表示可以取到，‘(’或‘)’表示取不到
    {
        a[k]=k;///存储2-n(a={0,0,2,3,4,5,6······}),创建一一对应关系
    }
    for (int i=1;i<=(k-1);i++)///遍历
    {
        if (a[i]!=0)
        {
            for (int j=2;j<(n/a[i])+1;j++)
            {
                a[i*j]=0;
            }
            sum+=1;
        }
    }
    cout<<sum;
    return 0;
}

有优化的方法请写在下面，谢谢~