Python【素数】

文章目录

• • Python【素数】
  • • 1.朴素方法
    • 2.普通筛
    • 3.埃式筛
    • 4.线性筛

Python【素数】

今天看到有好兄弟写了判断素数的几种方法，发现自己有点忘了线性筛，所以写一遍。

1.朴素方法

# 朴素方法就是从2到根号x去找是否有能整除x的数
# 如果有那么x为合数，否则x为质数
def is_prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
# 这种方法适合在只需要判断少量数是否为素数的情况

2.普通筛

# 普通筛，用每一个数去筛掉它的倍数（它的倍数肯定不是素数）
# 时间复杂度O(nlogn)
prime = [True] * 1001
def is_prime():
    for i in range(2, 1001):
        for j in range(i * 2,1001,i):
            prime[j] = False

3.埃式筛

# 埃式筛，用每一个素数去筛掉它的倍数（它的倍数肯定不是素数）
# 如果一个数是合数，那么它的倍数肯定在之前已经被它的因子筛过了
# 所以不再重复筛，比普通筛的效率提高了一些
# 时间复杂度O(nloglogn)
prime = [True] * 1001
def is_prime():
    for i in range(2, 1001):
        if prime[i]:
            for j in range(i * 2,1001,i):
                prime[j] = False

4.线性筛

# 线性筛，用每一个数的最小素因子去筛掉它
# 我们发现埃式筛种还有一些数可能会被多个素数筛掉
# 比如2、3都会筛6，这样也会造成重复筛
# 线性筛中每个数只会被筛一次，因此时间复杂度为O(n)
isprime = [True] * 1001
primes = []
def check():
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)    # i是素数，加入到素数列表
        j = 0
        while primes[j] * i <= 1000:
            isprime[primes[j] * i] = False  # 标记为非素数
            if i % primes[j] == 0:
                break
            j += 1
check()
print(primes)