本文将从算法、代码实现和时间复杂度三个方面详细介绍如何用Python输出1000以内的素数。

一、筛选法算法

筛选法算法，也叫埃氏筛法，是一种较为常用的素数筛法。简要思路是将2到n范围内所有数存入表中，从2开始，把2的倍数全部挖去，然后在剩下的数中再找到下一个未挖去的数，也就是素数3，再将3的倍数全部挖去，如此反复进行，直到筛子为空时结束。最后剩下的即为素数。

def sieve(n): is_prime = [True] * n is_prime[0] = False is_prime[1] = False for i in range(2, n): if is_prime[i]: for j in range(i ** 2, n, i): is_prime[j] = False return [x for x in range(n) if is_prime[x]] 

以上代码中，is_prime列表用于判断每个数是否为素数，is_prime[0]和is_prime[1]默认为False，因为0和1都不是素数。从2开始进行判断，如果某个数为素数，则将其倍数标记为False。最后返回为True的数即是素数。

二、代码实现

通过调用sieve(n)函数，即可输出1000以内的素数。

def main(): primes = sieve(1000) print(primes) if __name__ == '__main__': main() 

主函数中调用sieve(1000)函数，返回1000以内的素数。最后将结果打印输出。

三、时间复杂度

在筛选法算法中，时间复杂度为O(n*loglogn)。此处简单说明以下原因：从2到n的数中共有n-2个数，其中合数至少有相应的质因数。也就是说，对于任意小于n的素数p，2p,3p,4p,……kp（kp≤n）等这k个数都不是素数（其中k=[n/p]）。因此，算法复杂度为：n/2+n/3+n/5+……+n/p+……（p是从2到n的质数）。

按照解析：

$$ begin{aligned} &n/2+n/3+n/5+ldots+n/p+ldots \ =&n*(1/2+1/3+1/5+ldots+1/p+ldots) \ =&n * ln(ln(n)) end{aligned} $$

所以，总的时间复杂度为O(n*loglogn)。