欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python 判断素数(质数)的方法讲解

程序员文章站 2024-03-15 15:07:53
...

质数又称素数。指在一个大于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