实现isPrime()函数,参数为自然数,如果自然数是质数,返回True,否则返回False。
时间: 2023-06-25 19:08:11 浏览: 108
原型的函数prime,用来判断整数n是否为素数
以下是一个实现isPrime()函数的Python代码:
```python
def isPrime(n):
if n <= 1: # 1不是质数
return False
elif n <= 3: # 2和3都是质数
return True
elif n % 2 == 0 or n % 3 == 0: # 排除所有能被2或3整除的数
return False
i = 5
while i * i <= n: # 在范围内循环,检查是否有其他因子
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
```
这个函数首先排除了1和所有能被2或3整除的数,然后在剩下的数中循环,检查是否有其他因子。它使用了一个常用的优化技巧,即在循环中只检查形如6k±1的数。这是因为,除2和3以外的所有质数都可以表示为6k±1的形式。
阅读全文