判断是否是素数的代码,多写几种
时间: 2024-05-10 18:15:49 浏览: 61
判断是否是素数的代码有很多种写法,以下是其中几种常见的写法:
1. 基本判断法:从2到n-1逐个判断n是否能被整除,如果都不能整除,则n为素数。
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
```
2. 优化判断法1:只需要从2到n的平方根进行判断即可,因为如果n可以被大于它平方根的数整除,那么一定可以被小于它平方根的数整除。
```python
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
```
3. 优化判断法2:对于偶数可以直接判断,因为偶数中只有2是素数,其他都是合数。
```python
import math
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
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
```
4. 埃拉托斯特尼筛法:从2开始,将每个素数的倍数都标记成合数,直到筛完所有小于n的素数,剩下的就是素数。
```python
def eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
print(eratosthenes(100))
```
5. 线性筛法:相比于埃拉托斯特尼筛法,可以将每个合数只筛选一次,时间复杂度更低。
```python
def linear_sieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
if i * primes[j] > n:
break
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
return primes
print(linear_sieve(100))
```
阅读全文