python如何判断素数

Python 判断素数（质数）的方法讲解

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。素数在数论中有着很重要的地位。比 1 大但不是素数的数称为合数。1 和 0 既非素数也非合数，2 是素数。

1.判断是否是素数：import timeit from math import sqrt def isPrimes1(n): if n <= 1: return False for i in range(2, int(sqrt(n) + 1)): if n % i == 0: return False return True def isPrimes2(n): if n > 1: if n == 2: return True if n % 2 == 0: return False for x in range(3, int(sqrt(n) + 1), 2): if n % x == 0: return False return True return False print(timeit.timeit("isPrimes1(100)", setup="from chapter01 import isPrimes1", number=10000)) print(timeit.timeit("isPrimes2(100)", setup="from chapter01 import isPrimes2", number=10000))

2.求 n 以内的素数。import timeit from math import sqrt import copy def listPrimes1(n): """ 初始所有一个n维数组 res 表示数都为素数。 从3开始将3的奇数倍标记成False，即不是素数。 之后对每一个素数此行上一步操作 这里我们不用管偶数倍，因为我们最后判定时默认所有偶数不是素数 """ if n < 3: if n == 2: return [2] return None res = [True] * n for i in range(3, int(n ** 0.5) + 1, 2): res[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1) return [2] + [i for i in range(3, n, 2) if res[i]] def listPrimes2(n): ''' 计算n之内的素数 :param n: :return: ''' if n < 3: if n == 2: return [2] return None num_list = [x for x in range(2, n) if x%2 !

3.求 m 到 n 之间的素数。def mnPrimes1(m,n): if m == 1: num_list = [2] + [p for p in range(2, n) if p % 2 != 0 and 0 not in [p % d for d in range(2, int(sqrt(p)) + 1)]] if m >= 2: num_list = [p for p in range(m, n) if p % 2 != 0 and 0 not in [p % d for d in range(2, int(sqrt(p)) + 1)]] return num_list def mnPrimes2(m,n): num_list = [x for x in range(m, n) if x % 2 != 0 and x != 1] new_list = copy.copy(num_list) for i in num_list: for d in range(3, int(sqrt(i)) + 1, 2): if i % d == 0: new_list.remove(i) break if m == 2: new_list = [2] + new_list return new_list