439后面的397是质数吗是什么数字

来源：蜘蛛抓取(WebSpider) 时间：2022-10-22 01:16 标签： 397是质数吗

质数（又称素数）指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的作用。

质数的分布规律是以36N（N+1）为单位，随着N的增大，素数的个数以波浪形式渐渐增多。

更新了质数筛(包括轮式筛法), 修复了一些错误.

厉害吧, 就一行代码, .

如下所示, 这是3阶质数轮盘.

构成轮盘周长的那几个质数

质数只会出现在灰色区域.

那最内层灰色的数字是什么呢? 内层灰色的数字是和轮盘周长互为质数的数再加上构成轮盘周长的那几个质数(5阶轮盘就是 2,3,5,7,11 ). 注意是互质数, 而不是小于轮盘周长的质数.

所以外层灰色数字就等于内层灰色数字(除去构成轮盘周长的那几个质数, 再加个1)+轮盘周长.

那为什么质数就一定会出现在灰色区域呢?

b 一定是 的互质数.

所以质数只可能出现在灰色区域.

那我们应该这么写代码呢?

第一步肯定是生成轮盘, 也就是找互质数. 这里我们已经用另一个函数找到了, 我们就直接把5阶轮盘的互质数复制过来吧.

生成了最内层轮盘, 还要生成外层轮盘. 我们用一个循环, 每次让内层轮盘的值 +2310 , 就生成了外层循环.

所有灰色区域的值就存到了Prime2矩阵中.

这之后, 我们再用前面的筛法, 将其和轮式筛法结合起来.

不错不错, 测试一下?

先测试一下上一种方法求 10^7 以内的质数.

不错不错, 速度又快了 20\text{%} , 那我们还能不能再快一点呢?

啊这, 居然花了超级多时间在比较需要筛掉的数字和 的大小上. 我们得将代码再优化一下, 不要在比较大小上花太多时间.

那么我感觉到现在已经很难优化下去了啊, 我已经换了一种逻辑, 如果要继续优化, 要么自己发明一种大数快速乘法, 要么再换一种逻辑.

不过我们还是没有跑过标准库, 等我再研究研究吧, 我研究一下MATLAB是怎么写的, 用的什么逻辑

%寻找小于输入数(under)的所有质数

OK, 那就优化到这里吧. 来看一下我们以上进行的优化的成果.

经过以上13次优化, 效果还是很可观, 从最开始的跑不出到最后计算 10^7 以内的质数都在 0.1 秒附近.

虽然我们没有跑出和MATLAB内置函数一样的速度, 但是已经相对来说可以了.

CPU的性能是强大的, 经过优化, 代码是可以飞起来的, 当然, 最重要的不是优化代码, 而是写的时候就好好写呀.

最后, 来观摩一下MATLAB内置的函数吧.

我要回帖

更多关于 397是质数吗 的文章

 

随机推荐