嵌入式实验第二次课后作业

emmm……这次题目有点长,直接看图吧:

刚开始,感觉难的点就是求素数,毕竟数据量很大,五秒钟时间要把所有素数和弄出来感觉是很难的。首先,我用了一种最普遍的方法,代码如下:

int isPrime_1(int num)
{
    //两个较小数另外处理
    if(num == 2 || num == 3)
        return 1;
    //不在6的倍数两侧的一定不是质数
    if(num%6 != 1 && num%6 != 5)
        return 0;
    int tmp =sqrt(num);
    //在6的倍数两侧的也可能不是质数
    for(int i = 5;i <= tmp; i+=6)
        if(num%i == 0 || num%(i+2)==0)
            return 0 ;
    //排除所有,剩余的是质数
    return 1 ;
}

然后试了下零到一千万,直接破五秒

然后想到多开点线程,试了几下,在1000个线程每个线程算10000个数的时候是比较快的情况了,也要三秒多

对了,这里就是今天碰到的第一个坑(虽然和最后的程序一点关系都没):用循环去开线程的时候,会出现一堆线程传进去的参数一样的情况,解决方案:用数组来保存需要传的参,不要把正在循环里面变化的变量直接传过去

虽然要三秒多,但是好像是可行的,因为我并不用计算那九千万个数的和,只需要先算出一亿内所有素数之和存入程序,然后算出比大的数大的素数,比小的数小的素数之和,两者相减即可,也就是说,我的确只需要算大约一千万个素数之和

那么,问题来了:一亿素数之和是多少(摊手)

上网继续查资料,没想到,搜“一亿+素数”关键字还真能搜到东西,发现三个博客都说自己能半秒算出一亿以内素数

其中有一篇是java,不看,剩下两篇如下:

半秒内筛一亿以内的所有素数 (注意这篇标了转载但没标原文地址)

半秒求一亿内的素数:经典筛选法&线性筛选法的介绍、改进、实现与性能分析

先看第一篇,一看就是完全看不懂的代码,为了效率用了大量的位操作,代码自身毫无可读性,还好解析齐全,大概看了看,把代码复制了下来,但是还是不知道怎么用它,毕竟我要的是素数之和可是它输出的是素数个数,而我找不到哪个变量是确定为素数的数 o(╥﹏╥)o

再看第二篇,就相当简洁明了,是用空间换时间的策略。弄了下来,自己在外面套一个函数去算输入两数之间的素数之和。

等等,我好像是来找一亿素数之和大小的?怎么就半秒算出一亿素数之和了?

算了不管了,能用就行(狗头)

原本还想继续沿用之前的方案,先算出1亿存着,再减,应该可以减少一点点时间,但是转念一想,这是数组啊!题目中计时是从服务器接收到“GET”开始的,而这个函数在打开程序的时候就开始执行了啊,在这省时间已经毫无意义了。

对了,上面那个看不懂的代码也不是毫无用处,我准确地知道了一亿以内素数个数是5761455个,而不是第二篇里面估的500多万,可以缩小一点数组占用空间(虽然好像也没啥用)

到这里,终于解决了第一个问题:求解素数和,接下来第二个问题出现了

好的我忘了第二个出现的问题是什么了(大概下午有一个多小时失忆了),反正就是有一个不大不小的问题(理直气壮)

我突然想起来了(小声),是很新手的一个错误:在服务器返回两个数字并被客户端接收后,客户端从字符串中提取这两个数的时候就会程序崩溃,试了很多地方,最后发现我对第二个数结束判断符设的是‘:’,可是这个符号是客户端下次发送的时候才会加上的,这里应该直接用‘\0’来判断

接下来第三个问题,也是困扰我最久最让我没方向的一个问题:服务器需要在5s超时后给客户端发送TLL

一看这不简单,把客户端程序里面返回计算数据注释掉,服务器端拉出一个alarm(),写上中断处理函数(发送字符串),一试并不成功。接下来试了各种办法,比如在中断里面只改一个flag标志,在while里面去读取标志再处理啊什么的,都不行。后来上谷歌查了好久,终于读到有可能引发的错误:服务器不能向客户端连续发送信息。

于是花了半个小时写了个心跳包程序,在客户端那边起了个alarm,隔一秒钟给服务器发个包,服务器读到心跳包之后去看看时间有没有过五秒,没过忽略此消息,过了返回超时错误

最后加上写文件操作非常简单,不多说了

12/03更新

找到了为什么跳到alarm里面发送就失败的原因:fd在循环中不断增大,当跳到alarm中时变为了1024,直接在alarm中写死为4而不是fd即可

源代码下载地址(有密码的哦,等验收完再开放)

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注