Please calculate how many prime numbers are there between two integers a and b (including).




Input
There are some cases. Each line of input a b. 1 ≤ a < b ≤ 10000.



Output
If the result is a prime number, output "YES", else output "NO" in a single line.



Sample Input
1 3
5 9
1 1000


Sample Output
YES
YES
NO

是天大acm第4088题

1到1万也就1千多个质数，先全部取出存到数组中。

这样就会快很多了

我后来也是这么想的，但不知怎么做，这是我的代码，会超时

#include <iostream>
#include <stdio.h>
using namespace std;

bool isPrime(unsigned long n) {  
    if (n <= 3) {      
        return n > 1;  
    } else if (n % 2 == 0 || n % 3 == 0) {   
        return false;   
    } else {     
        for (unsigned short i = 5; i * i <= n; i += 6) {      
            if (n % i == 0 || n % (i + 2) == 0) {      
                return false;      
            }      
        }     
        return true;  
    }
}
int main(){
   
     int a[1299],i,t=0;
    for(i=2;i<10000;i++){
        if(isPrime(i)){
            a[t]=i;
            t++;
        }
    }
    int c,b,min=0,max=0;
   
    while(true){
        scanf_s("%d %d",&b,&c);
        for(i=0;i<1299;i++){
            if(i==0){
                if(a[0]>=b){
                    min=0;
  //                  cout<<"min1"<<min<<endl;
                }
            }

            if(i>=1){
                if(a[i]>=b&&a[i-1]<=b){
 //                   cout<<"min2"<<min<<endl;
                    min=i;
                }
                if(a[i]>=c&&a[i-1]<=c){

                    max=i;
  //                  cout<<"max"<<max<<endl;
                     break;
                }
            }

        }


        if((max-min)==1){
            cout<<"YES"<<endl;
        }
        if((max-min)!=1){
            cout<<"NO"<<endl;
        }
        
    }


    return 0;
}

你帮我看下代码怎么改

不到1300次的循环也超时！

不知，反正超时，估计是求素数的数组用了太多时间

也可能不能这么写，我也是没办法了

进去看了一下，Time Limit: 1.0 Seconds

再优化吧！

质数表加上二分查找

我这WA，待我先查查

AC了，你加油