在编程中怎么求素数

在编程中求素数主要有以下几种方法：

试除法

步骤：

首先判断给定的数 \（ n \） 是否小于 2，若小于 2 则不是素数，直接返回 false。

然后，从 2 开始依次用 \（ n \） 去除以 2 到 \（ \sqrt{n} \） 之间的每一个数，若存在能整除 \（ n \） 的数，则 \（ n \） 不是素数，返回 false；否则，\（ n \） 是素数，返回 true。

示例代码（Python）：

```python

def is_prime（n）:

if n < 2:

return False

for i in range（2, int（n0.5） + 1）:

if n % i == 0:

return False

return True

```

埃氏筛法

步骤：

创建一个长度为 \（ n+1 \） 的布尔数组 \（ isPrime \），并将所有元素初始化为 true。

从 2 开始遍历到 \（ \sqrt{n} \），对于每一个 \（ i \），如果 \（ isPrime[i] \） 为 true，即 \（ i \） 是素数，那么将从 \（ i \times i \） 开始，将 \（ i \） 的所有倍数标记为 false（即非素数）。

最后，遍历 \（ isPrime \） 数组，将值为 true 的下标即为素数。

示例代码（Python）：

```python

def sieve_of_eratosthenes（n）:

isPrime = [True] * （n + 1）

isPrime = isPrime = False

for i in range（2, int（n0.5） + 1）:

if isPrime[i]:

for j in range（i*i, n + 1, i）:

isPrime[j] = False

return [i for i in range（n + 1） if isPrime[i]]

```

米勒-拉宾素性测试

步骤：

选择一个随机数 \（ a \）（ \（ 2 \leq a \leq n-2 \））。

计算 \（ x = a^r \mod n \） 其中 \（ r \） 是小于 \（ n \） 的随机数。

如果 \（ x = 1 \） 或 \（ x = n-1 \），则 \（ n \） 可能是素数。

否则，重复 \（ r-1 \） 次：计算 \（ x = x^2 \mod n \），如果 \（ x = n-1 \），则 \（ n \） 可能是素数。

如果在所有 \（ r-1 \） 次迭代中 \（ x \） 都等于 \（ n-1 \），则 \（ n \） 是素数；否则，\（ n \） 不是素数。

示例代码（Python）：

```python

import random

def miller_rabin（n, k=5）:

if n <= 1 or n == 4:

return False

if n <= 3:

return True

if n % 2 == 0:

return False

r, s = 0, n - 1

while s % 2 == 0:

r += 1

s //= 2

for _ in range（k）:

a = random.randrange（2, n - 1）

x = pow（a, s, 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

```

建议

试除法适用于判断一个给定的数是否为素数，时间复杂度为 \（ O（\sqrt{n}） \）。

埃氏筛法适用于求解一定范围内所有素数的问题，时间复杂度为 \（ O（n \log \log n） \）。

米勒-拉宾素性测试是一种概率性算法，适用于大数素性测试，时间复杂度为 \（ O（k \log^3 n） \），其中 \（ k \） 是测试次数。