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))

判断执行时间：

0.00563765699999999
0.001561703999999997

后一种方法将除 2 之外的偶数排除，大大减少了执行时间。

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 != 0]

    new_list = copy.copy(num_list)
    # new_list = []
    for i in num_list:
        # new_list.append(i)
        for d in range(3, int(sqrt(i)) + 1,2):
            if i%d == 0:
                new_list.remove(i)
                break
    return [2] + new_list

def listPrimes3(n):
    '''
    计算n之内的素数
    :param n:
    :return:
    '''
    if n < 3:
     if n == 2:
         return [2]
     return None
  
    return [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)]]

print(timeit.timeit("listPrimes1(100)", setup="from chapter01 import listPrimes1",number=100))
print(timeit.timeit("listPrimes2(100)", setup="from chapter01 import listPrimes2", number=100))
print(timeit.timeit("listPrimes3(100)", setup="from chapter01 import listPrimes3", number=100))

整理得到三种实现方法，其中第一种方法执行时间最短。

0.000947919999999991
0.003774201000000005
0.004751936999999984

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