如何解决这种时间超限的问题？

Question

问题：0≤a≦b≤100000，a和b都是100的整数倍，将[a,b）划分为若干个大小为100的区间[x,x+100），输入a,b,输出每个区间内素数的数目。如：输入：0 200，输出：25 21。
注：（感觉是题目的问题，毕竟a可以等于b还用大小括号？）
我写成这样了：
#include <stdio.h>
int ff(int x){int j,i,p=0;
for(j=1;j<x;j++){
if(x%j==0) p++;}
if(x==0||x==1) p=3;
if(p<2)
return 1;
else return 0;

} int main(){
int j=0,k,i=0,n=0,d[999],a,b,p;
scanf("%d %d",&a,&b);

if(a==b) printf("%d",ff(a)); 
for(k=a;k<b;k=k+100){p=0;
    for(i=k;i<(k+100);i++){
    if(ff(i)) p++;    
    } 
    d[j]=p;j++;
    

}for(i=0;i<j;i++)
printf("%d ",d[i]);

    return 0;
}****

结果时间超限了！用了2000多ms。
我的疑问：是因为像100000这样的数运行太浪费时间了吗？又该如何改正？

Answer 1

你可以参考我这篇文章 里的 优化后的暴力求解：
https://blog.csdn.net/apple_53792700/article/details/127575792

#include <stdio.h>
#include <math.h>

class PrimeNumber {
        unsigned char list[2000000] = {3};
    public:
        void GetPrimeNumber( int b ) {
            for (  int i = 2 ; i * i  <= b ; i ++ ) {
                // 如果 i 是素数的话
                if ( IsPrimeNumber( i ) ) {
                    // 去除列表内 i 的倍数
                    for (  int j = 2 ;  ; j++ ) {
                        // 如果 i * j 超出需要求的列表范围就退出
                        if ( i * j > b ) {
                            break;
                        }
                        ResPN(i * j);
                    }
                }
            }
        }

        bool IsPrimeNumber( int x ) {
            if (Get_bit(list, x)) {
                return false;
            } else {
                return true;
            }
        }

    private:


        void SetPN( int x ) {
            Res_bit(list, x);
        }

        void ResPN( int x ) {
            Set_bit(list, x);
        }

        bool Get_bit( unsigned char * st,  int num ) {
            return ( st[(int)(num / 8)] & (0x01 << (num % 8) ) ) > 0 ? true : false ;
        }
        void Set_bit( unsigned char * st,  int num ) {
            st[(int)(num / 8)] |= (0x01 << (num % 8) ) ;
        }
        void Res_bit( unsigned char * st,  int num ) {
            st[(int)(num / 8)] &= ~(0x01 << (num % 8) ) ;
        }

};

int main() {
    int j = 0, k, i = 0, n = 0, d[999], a, b, p;
    PrimeNumber P;
    scanf("%d %d", &a, &b);
    //a = 0 ;
    //b = 200;
    P.GetPrimeNumber(b);
    if (a == b) printf("%d", P.IsPrimeNumber(a));
    for (k = a; k < b; k = k + 100) {
        p = 0;
        for (i = k; i < (k + 100); i++) {
            if (P.IsPrimeNumber(i)) p++;
        }
        d[j] = p;
        j++;

    }
    for (i = 0; i < j; i++)
        printf("%d ", d[i]);

}

代码测试结果：