ReAilis 2019-03-10 13:13 采纳率: 100%
浏览 328
已采纳

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

在作
数素数 (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条回答

  • threenewbee 2019-03-10 13:16
    关注

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

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

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决