怎样判断一个数为素数

本文主要是介绍怎样判断一个数为素数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 Falseif number <=3:return Trueif number % 2 == 0 or number % 3 == 0:return Falsei = 5while i * i <= number:if number % i == 0 or number % (i+2) == 0:return Falsei += 6return True

4.验证

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

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 优化”。通过避免不必要的检查，可以加快素数判断的速度，特别是在处理大整数时。