怎样判断一个数为素数

1.素数的定义

\quad 素数（Prime Number）是指大于1的自然数（正整数），且只能被1和它本身整除的数。

2.程序设计思路

\quad 1）特殊情况处理：首先，检查输入的整数是否小于等于1。素数的定义排除了小于等于1的数，所以如果输入小于等于1的数，可以直接返回False。
\quad 2）检查可能的因子：对于大于1的整数，需要从2开始逐个检查可能的因子，一直到这个数的平方根（√n）为止。这是因为如果一个数n有一个大于√n的因子，那么它必然也有一个小于√n的因子，因此不需要检查大于√n的数。
$\quad$3）逐个检查因子：从2开始，逐个检查这些可能的因子是否能整除给定的整数。如果找到一个能整除的因子，就可以确定这个数不是素数，返回False。如果没有找到任何能整除的因子，就可以确定这个数是素数，返回True。

3.程序实现

def is_prime(number):
    if number <=1:
        return False
    if number <=3:
        return True
    if number % 2 == 0 or number % 3 == 0:
        return False
    
    i = 5
    while i * i <= number:
        if number % i == 0 or number % (i+2) == 0:
            return False
        i += 6
    
    return True 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.验证

number1 = int(input("请输入一个整数："))
if is_prime(number1):
    print(f'{number1}是素数。')
else:
    print(f'{number1}不是素数。')
1
2
3
4
5

5.为什么要定义i=5

\quad 在高效的素数判断函数中，初始化 i=5 是一个优化技巧，用来跳过一些不必要的检查，从而加快素数判断的速度。这是因为大多数素数可以表示为6的倍数加1或加5（6n ± 1，其中 n 是非负整数）。因此，我们只需要检查这两种形式的数是否是素数，跳过其他情况，从而减少检查的次数。
具体地，函数中的 i 变量从5开始，然后在每次迭代中以步长6递增（即 i += 6），这是因为：
\quad i 为5时，表示6n - 1形式的数。
\quad i + 2 为7时，表示6n + 1形式的数。
\quad 这个方法将素数检查的精力集中在了可能是素数的6的倍数加1和加5的数字上，跳过了那些不可能是素数的数字，提高了算法的效率。
\quad 这是一种常见的素数检查优化方法，通常被称为“6k ± 1 优化”。通过避免不必要的检查，可以加快素数判断的速度，特别是在处理大整数时。