已经AC、代码还有个可以优化的地方，你自己看看。

#include <cstdio>
#include <cmath>
const int maxn = 10010;
int cnt[maxn] = {0};
int isPrime(int i);
int main() {

    cnt[0] = cnt[1] = 0;
    for (int i = 2; i < maxn; i++) {
        cnt[i] = cnt[i - 1] + isPrime(i);
    }
    int a,b;
    while (scanf("%d%d",&a,&b) == 2) {
        
        if (isPrime(cnt[b] - cnt[a - 1]))
            puts("YES");
        else
            puts("NO");
        
    }
    
    
    return 0;
}

int isPrime(int i) {
    
    if (i <= 1) return 0;
    int n = floor(sqrt(i) + 0.5);
    for (int j = 2; j <= n; j++) {
        
        if (!(i % j)) return 0;
        
    }
    return 1;
}

收到的鲜花

• lowrie 于 2015-03-31 17:06 送鲜花  3朵   附言：我很赞同

思路就是尽量减少冗余的运算。cnt[i]用来表示从1到i有几个素数。所以求a到b有几个素数就是cnt[b] - cnt[a-1].

有个利用素数数组，来判断一个数是否为素数，是素数则加入到素数数组中，根据这个方法构造素数数组.....解决这题完全没问题





int a[100000];
int isprime(int len,int num)
{
    int i=0,x=sqrt(num);
   while(i<len)
   {
       if(num%a[i]==0) return 0;
       if(a[i]>x) break;
       i++;
   }
        return 1;
}
void makeprime(int num)
{
    int i,j=1,k;
    a[0]=2;
    k=a[0]+1;
    while(j<num)
    {
        if(isprime(j,k))
        {
            a[j]=k;
            j++;
        }
        k++;
    }

}

上面算法构造10万个素数都不会超时的

我能把英语全翻译完整，就是没有完全弄明白题意。我对这个题有兴趣做出来！希望共同讨论

好难

能把代码发下吗，新手，刚接触acm和数据结构

#include <stdio.h>
#include <stdbool.h>

#define COUNT   1231

int ans[COUNT] = { 0, 2, 3, 5, 7, 11, 13, 17, 19 };

/*

 * 二分查找，返回不大于value的最大坐标

 */
int BinarySearch(int value)
{
    int begIndex = 0;
    int endIndex = COUNT - 1;
    int midIndex = -1;

    while (begIndex <= endIndex)
    {
        midIndex = (begIndex + endIndex) / 2;

        if (ans[midIndex] == value)
        {
            return midIndex;
        }
        if (midIndex == begIndex)
        {
            return midIndex;
        }

        if (ans[midIndex] < value)
        {
            begIndex = midIndex;
        }
        if (ans[midIndex] > value)
        {
            endIndex = midIndex;
        }
    }
}

/*

 * 初始化质数表

 */
void InitArray()
{
    int length = 9;
    unsigned i, n;

    for (n = 23;length < COUNT;n += 2)
    {
        bool flag = true;
        for (i = 1;ans[i] * ans[i] <= n;i += 1)
        {
            if (n % ans[i] == 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)  ans[length++] = n;
    }
}

int main(void)
{
    int a, b;
    int aIndex = 0, bIndex = 0, dist = 0;

    InitArray();
    while (scanf("%d%d", &a, &b) == 2 && 1 <= a && a <= b && b <= 10000)
    {
        aIndex = BinarySearch(a);
        bIndex = BinarySearch(b);
        if (ans[aIndex] == a)  aIndex -= 1;

        dist = bIndex - aIndex;   // a， b 间质数的个数
        printf("%s\n", dist && dist == ans[BinarySearch(dist)] ? "YES" : "NO");
    }
    return 0;
}

没注意你的方法也行，结贴是没看见

就没一个用素数筛的

#include <stdio.h>

#define R    10000

int main()
{
    int a[R + 1] = {1, 1}, b[R + 1] = {0}, i, j;
    
    for(i = 1; ++i <= R; b[i] = b[i - 1] + !a[i])
    if(!a[i])for(j = i; (j += i) <= R; a[j] = 1);

    for(; scanf("%d%d", &i, &j) != EOF; puts(a[b[j] - b[i - 1]] ? "NO" : "YES"));

    return 0;
}