Problem Description
今天,小猪猪学习了新的知识,孤儿数,孤儿数就是除了1和他本身,其他数都不是他的因子.他发现,这些孤儿数的分布是有规律的,如果一个区间[l,r]中有超过1/3的孤儿数,那这个区间就是孤儿区间.你知道怎么判断一个区间是不是孤儿区间吗?
Input
第一行:T,表示有T组数据(T<=10);

下面T行,每行两个数字l,r,你需要判断[l,r]是不是一个孤儿区间.

(l,r<1e9,当l>=1000时,保证区间长度>=100,所以你可不能暴力求素数哦!)
这里提供一个筛素数的模板,你可能需要用,用法如下,(仔细点别抄错了...):
/*
* 素数筛选，判断小于 MAXN 的数是不是素数。
* notprime 是一张表，为 false 表示是素数，true 表示不是素数
*/
const int MAXN=1000010;
bool notprime[MAXN];//值为 false 表示素数，值为 true 表示非素数
void init() {
  memset(notprime,false,sizeof(notprime)); //需要#include<string.h>头文件
  notprime[0]=notprime[1]=true;
  for(int i=2; i<MAXN; i++)
    if(!notprime[i]) {
      if(i>MAXN/i)continue;
      for(int j=i*i; j<MAXN; j+=i)
        notprime[j]=true;
    }
}



int main(){
init();
/*------这里写你的代码....*/
}

Output
如果区间是孤儿区间,输出"YES",否则输出"NO"
Sample Input
1
2 3
Sample Output
YES

这个题目的输入案例太少了 给我整烦死

#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
const int maxn=1e6+1;
ll l,r;
int prime[maxn],cnt,ans;
bool vis[maxn];
inline void Gprime()
{
    for(re int i=2;i<=50000;++i)
    {
        if(!vis[i])prime[++cnt]=i;
        for(re int j=1;i*prime[j]<=50000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

ll shuru(){
   
   
 ios::sync_with_stdio(false);
    //cin>>l>>r;
    l=l==1?2:l;
    Gprime();
    memset(vis,0,sizeof(vis));
    for(re int i=1;i<=cnt;++i)
    {
        ll p=prime[i],start=(l+p-1)/p*p>2*p?(l+p-1)/p*p:2*p;
        for(re ll int j=start;j<=r;j+=p)vis[j-l+1]=1;
    }
    for(re int i=1;i<=r-l+1;++i)if(!vis[i])ans++;
    //cout<<ans;
 
    return ans;
   
}

int t;
bool res[100];

int main()
{
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>l>>r;
        int all=r-l+1;
       // cout<<shuru();
       //cout<<all<<endl;
       //cout<<shuru()<<endl;
        if(shuru()*3>all) res[i]=true;
        else res[i]=false;
    }
    for(int i=0;i<t;i++){
        if(res[i]) cout<<"YES"<<" ";
        else cout<<"NO"<<" ";
    }

   
}


大可不用看我的代码

供参考：

//Sample Input
//1
//2 3
//Sample Output
//YES
#include <stdio.h>
#include <string.h>
/*
* 素数筛选，判断小于 MAXN 的数是不是素数。
* notprime 是一张表，为 false 表示是素数，true 表示不是素数
*/
const int MAXN = 1e9-1;
bool   notprime[MAXN];//值为 false 表示素数，值为 true 表示非素数
void init() {
    memset(notprime, false, sizeof(notprime)); //需要#include<string.h>头文件
    notprime[0] = notprime[1] = 1;
    for (int i = 2; i < MAXN; i++)
        if (!notprime[i]) {
            if (i > MAXN / i)continue;
            for (int j = i * i; j < MAXN; j += i)
                notprime[j] = true;
        }
}
int main() 
{
    init();
    /*------这里写你的代码....*/
    int T, l, r, i, cnt;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &l, &r);
        cnt = 0;
        for (i = l; i <= r; i++)
            if (!notprime[i])cnt++;
        if (cnt > (r - l + 1) / 3)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

厉害，会用埃拉托斯特尼筛法生成素数表了。
疑惑，却不会区间素数的判断。

啊 你这个内存超了 Memory Limit Exceeded
埃式法 这个模板是我很久以前找的
现在重新学了一遍 好多不清楚了