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 Falsereturn 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 = 0while primes[j] * i <= 1000:isprime[primes[j] * i] = False  # 标记为非素数if i % primes[j] == 0:breakj += 1
check()
print(primes)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！