• Python

  • Python 判断质数（Prime Number）

  • @ 2025-5-17 21:16:17

Python 质数判断与因子统计教程（0基础）

1. 质数的基本概念

质数（素数）是大于1的自然数，且除了1和它本身外没有其他因数。例如：2、3、5、7是质数，而4、6、8不是。

2. 不优化的质数判断方法

定义法：遍历所有可能的因子，逐一检查。

def is_prime(n):
    # 处理小于等于1的数
    if n <= 1:
        return False
    # 处理2的情况
    if n == 2:
        return True
    # 处理偶数
    if n % 2 == 0:
        return False
    # 遍历所有可能的因子（从3到n-1的奇数）
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    return True

# 测试
print(is_prime(7))  # 输出: True
print(is_prime(8))  # 输出: False

关键点解释：

  • 特殊情况处理：小于等于1的数直接返回False，2单独处理。
  • 偶数排除：如果是偶数且不是2，直接返回False。
  • 遍历范围：从3开始到n-1，步长为2（只检查奇数）。

3. 统计因子数量

枚举法：遍历所有可能的因子，统计数量。

def count_factors(n):
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count

# 测试
print(count_factors(12))  # 输出: 6（因子：1, 2, 3, 4, 6, 12）
print(count_factors(7))   # 输出: 2（因子：1, 7）

关键点解释：

  • 遍历范围：从1到n，检查每个数是否能整除n。
  • 质数判断条件：如果因子数量为2，则n是质数。

4. 优化的质数判断方法

优化思路：只需检查到√n即可，因为如果n有一个大于√n的因子，则必然有一个小于√n的因子。

import math

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只需检查到sqrt(n)
    max_divisor = int(math.sqrt(n)) + 1
    for i in range(3, max_divisor, 2):
        if n % i == 0:
            return False
    return True

# 测试
print(is_prime_optimized(101))  # 输出: True
print(is_prime_optimized(100))  # 输出: False

性能对比：

  • 未优化：时间复杂度O(n)
  • 优化后：时间复杂度O(√n)

5. 优化的因子统计方法

优化思路：因子是成对出现的（例如，若i是n的因子，则n/i也是），只需遍历到√n。

import math

def count_factors_optimized(n):
    if n < 1:
        return 0
    count = 0
    sqrt_n = int(math.sqrt(n))
    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            # 如果i和n/i相同（即n是完全平方数），只算一个因子
            if i == n // i:
                count += 1
            else:
                count += 2  # 同时计数i和n/i
    return count

# 测试
print(count_factors_optimized(12))  # 输出: 6
print(count_factors_optimized(16))  # 输出: 5（因子：1, 2, 4, 8, 16）

关键点解释：

  • 遍历范围：从1到√n。
  • 完全平方数处理：如果i等于n/i，只算一个因子（例如，16的因子4只算一次）。

6. 综合应用：枚举质数

结合优化算法，枚举指定范围内的所有质数。

import math

def generate_primes(n):
    primes = []
    for num in range(2, n + 1):
        if is_prime_optimized(num):
            primes.append(num)
    return primes

# 测试
print(generate_primes(20))  # 输出: [2, 3, 5, 7, 11, 13, 17, 19]

7. 总结

方法 时间复杂度 适用场景
朴素质数判断 O(n) 小规模数的简单判断
优化质数判断 O(√n) 大规模数或频繁判断
朴素因子统计 O(n) 因子数量少的情况
优化因子统计 O(√n) 快速统计大数值的因子

8. 练习题

  1. 判断质数：编写函数判断输入的数是否为质数。
  2. 统计因子：编写函数统计输入数的因子数量。
  3. 枚举质数：生成1到100之间的所有质数。

答案示例：

# 练习1
print(is_prime_optimized(29))  # 输出: True

# 练习2
print(count_factors_optimized(28))  # 输出: 6

# 练习3
print(generate_primes(100))  # 输出: [2, 3, 5, 7, ..., 97]

通过这些优化方法，你可以在处理大数时显著提高程序效率。

15 条评论

  • @ 2025-5-20 20:30:57

    在这段代码中，函数的核心功能是判断一个数是否为回文数。以下是添加了详细注释的代码：

    import math

def HuiWenShu(n):
    """判断一个数是否为回文数"""
    # 备份原始数值用于后续比较
    bf = n
    # 初始化位数计数器
    cnt = 0
    # 计算数字的位数
    while bf != 0:
        bf //= 10  # 整除10去掉最低位
        cnt += 1   # 位数加1
    
    # 恢复备份值用于下一步计算
    bf = n
    # 初始化反转后的数值
    res = 0
    
    # 反转数字的每一位
    while bf != 0:
        # 获取当前最低位，乘以10的相应次幂，累加到结果中
        res += bf % 10 * math.pow(10, cnt - 1)
        bf //= 10  # 整除10去掉最低位
        cnt -= 1   # 剩余位数减1
    
    # 比较原数和反转后的数是否相等
    if n == res:
        return True
    else:
        return False

# 测试示例
print(HuiWenShu(12321))  # 输出: True

    主要注释说明：

    1. 函数定义处添加了文档字符串，说明函数功能
    2. 对关键变量如bf、cnt、res的作用进行了解释
    3. 在两个主要循环处，分别解释了计算位数和反转数字的逻辑
    4. 对核心计算步骤res += ...进行了详细说明
    5. 添加了测试示例和预期输出注释

    这样的注释可以帮助其他开发者快速理解代码的工作原理和实现逻辑。

    • @ 2025-5-20 20:30:09 
      import math
def HuiWenShu(n):
    """判断一个数是否为回文数"""
    # 备份原始数值用于后续比较
    bf = n
    # 初始化位数计数器
    cnt = 0
    # 计算数字的位数
    while bf != 0:
        bf //= 10  # 整除10去掉最低位
        cnt += 1   # 位数加1
    # 恢复备份值用于下一步计算
    bf = n
    # 初始化反转后的数值
    res = 0
    # 反转数字的每一位
    while bf != 0:
        # 获取当前最低位，乘以10的相应次幂，累加到结果中
        res += bf % 10 * math.pow(10, cnt - 1)
        bf //= 10  # 整除10去掉最低位
        cnt -= 1   # 剩余位数减1
    # 比较原数和反转后的数是否相等
    if n == res:
        return True
    else:
        return False
# 测试示例
print(HuiWenShu(12321))  # 输出: True
      • @ 2025-5-20 20:13:07 
        #判断是否为素数
def     ZhiShu(n):   # ①        (n):             
    for i in range(2,n):
        if    n%i==0:  #   ②        :      
            break
    else:
        return True
#判断是否为回文数
def HuiWenShu(n):
    n=str(n)
    if n==     n[::-1]:  # ③        :
    #if n == "".join(reversed(n)):
        return True
    else:
        return False
for i in range(11,1001):
    if ZhiShu(i)==True    and HuiWenShu(i) == True:#     ④        :
        print('{}是回文素数！'.format(i))
        • @ 2025-5-20 20:08:04 
          #判断是否为素数
def     ZhiShu(n):   # ①        (n):             

    for i in range(2,n):

        if    n%i==0:  #   ②        :
            
            break

    else:

        return True
print(bool(ZhiShu(100)))
print(ZhiShu(100))
          • @ 2025-5-20 20:07:22 

            #判断是否为素数
def     ZhiShu(n):   # ①        (n):             

    for i in range(2,n):

        if    n%i==0:  #   ②        :
            
            break

    else:

        return True
print(bool(ZhiShu(100)))
            • @ 2025-5-20 19:52:02

              • @ 2025-5-20 19:50:01 
                import math
n = int(input())
#t = int(math.sqrt(n))
flag = True#假设它是质数
#for i in range(i,t+1):
i = 2
while i*i<=n:
    if n%i == 0:
        flag = False
        break
    i+=1
if flag == True and n >= 2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                • @ 2025-5-20 19:34:56 
                  import math
n = int(input())
t = int(math.sqrt(n))
flag = True#假设它是质数
for i in range(2,t+1):
    if n%i == 0:
        flag = False
        break
if flag == True and n >= 2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                  • @ 2025-5-20 19:15:49 
                    n = int(input())
flag = True#假设它是质数
for i in range(2,n):
    if n%i == 0:
        flag = False
        break
if flag == True and n >= 2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                    • @ 2025-5-20 19:07:42 
                      n = int(input())
flag = True#假设它是质数
for i in range(2,n):
    if n%i == 0:
        flag = False
        break
if flag == True and n >= 2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                      • @ 2025-5-20 19:05:18 
                        n = int(input())
flag = True#假设它是质数
for i in range(2,n):
    if n%i == 0:
        flag = False
        break
if flag == True:
    print(n,"是质数")
else:
    print(n,"不是质数")
                        • @ 2025-5-20 18:58:49 
                          n = int(input())
cnt = 0
for i in range(1,n+1):#[1,n]  ->   [2,n-1]
    if n%i == 0:
        cnt+=1
if cnt == 2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                          • @ 2025-5-20 18:49:36 
                            n = int(input())
cnt = 0
for i in range(1,n+1):
    if n%i == 0:
        cnt+=1
if cnt==2:
    print(n,"是质数")
else:
    print(n,"不是质数")
                            • @ 2025-5-17 21:35:21
                              已修改

                              🐍 Python 判断质数（素数）教程

                              🔍 什么是质数？

                              质数（也叫素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。换句话说，一个质数只能被1和它自己整除。

                              举例：

                              • 2, 3, 5, 7, 11, 13, 17, 19, 23... 是质数
                              • 4, 6, 8, 9, 10, 12... 不是质数（因为它们可以被其他数整除）

                              ⚙️ 如何判断一个数是否为质数？

                              方法一：最简单的暴力枚举法

                              对于给定的正整数 n，我们可以从 2 开始检查到 √n，如果在这期间没有找到能整除 n 的数，则 n 是质数。

                              为什么只检查到 √n？ 因为如果 n 可以分解成两个因子 a * b = n，那么其中一个因子必然小于等于 √n。

                              📦 实现质数判断的几种方法

                              ✅ 方法一：简单暴力枚举

                              import math

def is_prime_simple(n):
    if n <= 1:
        return False  # 小于等于1的不是质数
    for i in range(2, int(math.sqrt(n)) + 1):  # 检查从2到√n的所有数
        if n % i == 0:                         # 如果n能被i整除
            return False                       # 则n不是质数
    return True                                # 如果没有找到任何因数，n是质数

# 测试代码
print(is_prime_simple(11))  # 输出: True
print(is_prime_simple(15))  # 输出: False

                              ✅ 解释：

                              • 对于每个数 n，我们只需要检查到 √n
                              • 如果 n 能被某个数 i 整除，说明 n 不是质数
                              • 否则，n 是质数

                              ✅ 方法二：优化后的暴力枚举（减少偶数检查）

                              import math

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:
        return True  # 2是唯一的偶数质数
    if n % 2 == 0:
        return False  # 其他偶数都不是质数
    
    # 只检查奇数
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

# 测试代码
print(is_prime_optimized(11))  # 输出: True
print(is_prime_optimized(15))  # 输出: False

                              ✅ 解释：

                              • 首先排除所有偶数（除了2）
                              • 然后只检查奇数
                              • 这样可以减少一半的计算量

                              ✅ 方法三：埃拉托斯特尼筛法（Sieve of Eratosthenes）

                              这种方法适合用来找出一定范围内的所有质数。

                              def sieve_of_eratosthenes(limit):
    """返回小于等于 limit 的所有质数"""
    if limit < 2:
        return []
    
    # 初始化布尔数组，默认值为 True
    prime = [True] * (limit + 1)
    p = 2
    while (p * p <= limit):
        # 如果 prime[p] 没有被标记过，说明 p 是质数
        if prime[p]:
            # 标记所有 p 的倍数为非质数
            for i in range(p * p, limit + 1, p):
                prime[i] = False
        p += 1
    
    # 收集所有的质数
    primes = [p for p in range(2, limit + 1) if prime[p]]
    return primes

# 测试代码
primes_up_to_30 = sieve_of_eratosthenes(30)
print(primes_up_to_30)  # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

                              ✅ 解释：

                              • 使用一个布尔数组来记录每个数是否为质数
                              • 从最小的质数开始，将其所有倍数标记为非质数
                              • 继续处理下一个未被标记为非质数的数
                              • 最终剩下的未被标记的数就是质数

                              ✅ 方法四：米勒-拉宾素性测试（Miller-Rabin Primality Test）

                              这是一种概率算法，适用于大数的质数检测。这里提供一个简化版实现：

                              import random

def miller_rabin(n, k=40):
    """使用 Miller-Rabin 算法判断 n 是否为质数，k 为测试次数"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    # 写 n-1 为 d*2^r 的形式
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # 见证者循环
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# 测试代码
print(miller_rabin(11))  # 输出: True
print(miller_rabin(15))  # 输出: False

                              ✅ 解释：

                              • 米勒-拉宾测试是一种基于费马小定理的概率算法
                              • 它通过多次随机选择“见证者”来测试数是否为质数
                              • 增加测试次数可以提高结果的准确性

                              🎨 可视化图解说明（伪代码风格）

                              is_prime(n):
│
├─→ 如果 n ≤ 1 返回 False
│
├─→ 如果 n = 2 返回 True
│
├─→ 如果 n 是偶数且 n ≠ 2 返回 False
│
└─→ 对于 i = 3 到 √n 步长为 2:
        如果 n % i == 0 返回 False
    返回 True

                              🧰 质数判断小技巧总结

                              技巧 说明
                              🚫 快速排除 小于等于1的数直接排除；2是唯一的偶数质数
                              🔄 循环优化 只需检查到 √n；跳过偶数可减少一半计算量
                              🧩 数学原理 基于费马小定理的米勒-拉宾测试适合大数

                              🧪 练习建议

                              你可以试着挑战以下问题：

                              • [ ] 找出 1~100 中所有的质数
                              • [ ] 编写一个函数，返回第 n 个质数
                              • [ ] 用埃拉托斯特尼筛法生成质数表，并查找指定范围内的质数
                              • [ ] 使用米勒-拉宾测试判断大数是否为质数

                              📚 推荐学习路线图

                              质数入门 👉 简单暴力枚举 👉 优化枚举 👉 埃拉托斯特尼筛法 👉 米勒-拉宾测试

                              🙋‍♂️ 如何继续学习？

                              如果你希望我继续扩展以下内容，请告诉我：

                              • 如何结合其他算法（如动态规划）解决更复杂的问题？
                              • 如何用类封装质数判断函数？
                              • 如何画出质数判断过程帮助理解？
                              • 如何进一步优化质数判断算法？

                              😊

                              📌 结语：
                              质数是数学中的一个重要概念，在编程中也有广泛的应用。掌握质数判断不仅可以加深对数学的理解，还能提升编程能力！

                              需要配套练习题或进阶讲解也可以随时告诉我哦 😊

                              • @ 2025-5-17 21:17:09

                                Python 判断质数的详细教程（从零基础开始）

                                在这个教程中，我们将学习如何使用Python判断一个数是否为质数。我们将涵盖四种方法：定义法、不优化的枚举法、统计因子数量的方法以及优化后的枚举法。每种方法都将从概念解释到具体实现，并提供代码示例。

                                一、什么是质数？

                                质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。例如，2, 3, 5, 7, 11等都是质数。

                                质数的特点：

                                • 最小的质数是2，也是唯一的偶数质数。
                                • 大于2的所有偶数都不是质数（因为它们都可以被2整除）。
                                • 所有的质数都只能被1和自身整除。

                                二、Python 实现

                                方法 1：定义法（直接根据定义）

                                这是最直接的方法，检查从2到该数减1的所有数，看看是否有能整除该数的因子。如果有，则该数不是质数；如果没有，则它是质数。

                                def is_prime_basic(n):
    """使用定义法判断n是否为质数"""
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# 测试代码
test_number = 29
if is_prime_basic(test_number):
    print(f"{test_number} 是质数")
else:
    print(f"{test_number} 不是质数")

                                注意：

                                这种方法效率较低，尤其是当n很大时，需要进行大量的除法运算。

                                方法 2：不优化的枚举法（改进的定义法）

                                我们可以通过减少不必要的检查来提高效率。但是，在这个例子中，我们不会应用任何数学上的优化，只是简单地将范围缩小到sqrt(n)。

                                import math

def is_prime_naive_optimized(n):
    """不完全优化的枚举法判断n是否为质数"""
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 测试代码
test_number = 29
if is_prime_naive_optimized(test_number):
    print(f"{test_number} 是质数")
else:
    print(f"{test_number} 不是质数")

                                方法 3：统计因子数量的方法

                                通过计算一个数有多少个因子来判断它是否为质数。如果一个数只有两个因子（1和它自己），那么这个数就是质数。

                                def count_factors(n):
    """统计n的因子数量"""
    count = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            count += 1
            if i != n // i:  # 如果i不是平方根，则另一个因子也计入
                count += 1
    return count

def is_prime_by_factor_count(n):
    """通过统计因子数量判断n是否为质数"""
    if n <= 1:
        return False
    return count_factors(n) == 2

# 测试代码
test_number = 29
if is_prime_by_factor_count(test_number):
    print(f"{test_number} 是质数")
else:
    print(f"{test_number} 不是质数")

                                方法 4：枚举优化法（完全优化）

                                利用数学特性进一步优化判断过程。我们知道所有大于3的质数都可以表示为 6k±1 的形式。因此，我们可以只检查这些可能的因子。

                                import math

def is_prime_optimized(n):
    """使用完全优化的枚举法判断n是否为质数"""
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True  # 2和3是质数
    if n % 2 == 0 or n % 3 == 0:
        return False  # 排除2和3的倍数
    
    # 检查形如6k±1的形式
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

# 测试代码
test_number = 29
if is_prime_optimized(test_number):
    print(f"{test_number} 是质数")
else:
    print(f"{test_number} 不是质数")

                                三、总结与比较

                                方法 描述 优点 缺点
                                定义法 直接检查从2到n-1的所有数 简单易懂 效率低，尤其对大数
                                不优化的枚举法 将检查范围缩小到sqrt(n) 比定义法高效 仍然可以更高效
                                统计因子数量 通过统计因子数量来判断 直观理解质数的本质 计算量较大
                                枚举优化法 利用数学特性进一步优化 高效，适合大数 实现稍微复杂

                                四、练习题

                                练习 1：编写一个函数，输入一个正整数n，返回小于等于n的所有质数列表。

                                提示：可以使用上述任意一种方法结合循环来实现。

                                练习 2：编写一个函数，输入两个正整数start和end，输出这个区间内所有的质数。

                                提示：可以先实现一个判断质数的函数，然后遍历给定区间内的每个数并调用该函数。

                                希望这份教程对你有所帮助！如果你有任何疑问或需要进一步的帮助，请随时提问。😊

                                • 1
                                428
                                已通过
                                0
                                题解被赞
                                1. 关于
                                2. 联系我们
                                3. 隐私
                                4. 服务条款
                                5. 版权申诉
                                6. Language
                                7. 兼容模式
                                8. 主题
                                4. 在线咨询
                                5. Worker 0, 37ms
                                6. Powered by Hydro v4.13.3 Community