当前位置：新励学网 > 秒知问答 > 计算机怎么求质数

计算机怎么求质数

发表时间：2024-08-23 13:58:25 来源：网友投稿

完全遍历法：这种算法比较基本，对于每个数n，将n依次从2除到n，然后对余数进行比较，如果余数是0，则除得尽，如果不是0则除不尽，按照质数的定义，只有1和他本身能成为因数也就是除得尽，所以只有除得尽的数不大于两个时，才能是质数。

这种算法的好处是符合大多数人的第一反应，和定义契合得比较好，也比较省空间，但问题是假如我这里n输入了1000000+时，这个运算时间是非常长的，其算法复杂度高达1*10^12,小数据可以用遇到大数据就很难实现高效了。开根号遍历法仔细分析算法我们会发现，其实在做除法运算时不需要除每一个数，只要除到根号n即可。这是因为当除数大于根号n时，其结果肯定是小于根号n的（可以用反证法证明），假如此时能除得尽，那么该种可能早就在小于根号n的遍历中被排除掉了，就没有意义了。这样就减小了一部分算法复杂度。筛选法筛选法的核心是牺牲内存换速度，因为其不通过遍历来表达一列数而是直接通过数组来表达。用静态的bool量去变现数的状态。其核心流程为：定义一个bool数组，其下标为我们要判断的数，其值为true。表示初始阶段所有数都假定是素数。开始对这个数组进行筛选（及把值改为false），实现把因数含有2的所有数筛掉，把因数含有3的数筛掉，把因数含有5的数筛掉…一直筛选到只剩下素数为止。这种方法运算效率非常高，特别是在十万级以上的数中，其牺牲掉的内存不多，但对速度的提升确实是非常显著的。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！