上篇文章向大家介绍的判断质数是的方法,虽然可以很好的判断一个数是否为素数。但是如果遇到了这样的题,也难免会超时。
题目描述
输出 2 - n 之间所有的素数。(包含 2 和 n )
如果这种问题还采用一一判断的话,时间复杂度显然为O(N*N),如果时间限制是 1 s。当 N 大于 10000 就非常悬了,在加上一个 0 那就没有悬念直接超时了。
这个时候我们就需要更精进的算法————素数表。
它的核心思想是,任何合数可以通过素数(或合数)的乘积表示,而素数都(除了1和自身)不可以。
说白了实现过程就是遇到素数就要把它的倍数记做合数,遇到合数跳过。首先默认所有数为素数,0、1记做合数,从 2 开始遍历,直到 n 。
说了这么多还是要用代码实现
联系客服