筛选法求质数

给定一个整数n，求n以内的所有质数

基本思路：从2开始，依次将n以内的所有质数的倍数筛选掉，剩下的即为质数

Python实现：

def getPrimes(n):
    primeFlag = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if primeFlag[p]:
            primeFlag[p * 2:n + 1:p] = [False] * (n // p - 1)
        p += 1
    primeList = [i for i in range(2, n + 1) if primeFlag[i]]
    return primeList


print(getPrimes(100))

输出：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

优化：
i的倍数中包含了2i, 3i,…(i-1)i，这些数已经被比i小的数的倍数筛选过一次了，可以直接从i^2开始筛选

primeFlag[p * 2:n + 1:p] = [False] * (n // p - 1)

改为

primeFlag[p * p:n + 1:p] = [False] * ((n - p * p) // p + 1)