为什么用素数表来求素数反而比暴力求解还要来得慢?

在作
数素数 (20 分) Pi表示第 i 个素数。现任给两个正整数 M≤N≤10^4 ,请输出 P M 到 P N 的所有素数
这一题时,
使用了构造素数数组的方法,
之后每次在判断obj是否为素数时,只需要拿素数表中的数来判断即可,如果obj是素数,则也加入这个素数表中。
可是提交后发现这一方法超时
随后网络搜索解答发现判断obj是否为素数时,直接使用2到sqrt(obj)来逐一判断反而可以通过。
因不解故来询问一下

#include <stdio.h>

void printall( int N, int M, int*prime, int size );
int isprime( int obj, int* prime, int size );

int main ()
{
    int N = 0;
    int M = 0;
    scanf("%d %d",&M,&N);       //要求输出第M到第N个素数 
    int prime[N];   //素数表
    prime[0] = 2;
    int size = 1;   //素数表中的素数数量
    int obj = 3;

    while( size<N ) {
        if( isprime(obj, prime, size) ) { //判断obj是否为素数
            prime[size] = obj;
            size++;
        }
        obj += 2;
    }

    printall( N, M, prime, size );//按题目要求输出

    return 0;
 } 

    void printall( int N, int M, int*prime, int size ) { 
    for( int i = 0; i<size; i++ ) {
        if( i>=M-1 && i<N ) {
            printf("%d",prime[i]);
            if( i!=N-1 ) 
            printf("%c",(i+2-M)%10 == 0?'\n':' ');}
    }
} 

int isprime( int obj, int* prime, int size ) {
    int flag = 1;
    for( int i = 0; i<size; i++ ) {
        if( obj%prime[i] == 0 ) {
            flag = 0;
            break;
        }
    }
    return flag;
}

以上是使用素数表求解的全部代码
接下来将isprime()函数替换为直接求解的方式,反而得到了通过

int isprime( int obj ) {
    int flag = 1;
    for( int i = 2; i<=sqrt(obj); i++ ) {
        if( obj%i == 0 ) {
            flag = 0;
            break;
        }
    }
    return flag;
} 

1个回答

用素数表,在范围比较小的时候,和直接求差别不大
只求一个的话,差别也不大。

如果对一个比较大的数字判断,而且判断多次,那么优势就有了。

更何况,素数表需要访问数组,如果数组比较大,超过了cpu的缓存,从内存里取的话,这个会浪费几百上千的时钟周期,而还不如直接计算来的快。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问