在编程中求质数，有多种方法可以实现。以下是几种常见的方法及其公式：
1. 穷举法
穷举法是最简单直接的方法，通过遍历从2到给定上限的所有整数，并检查它们是否为质数。时间复杂度为O（N^2），其中N是上限。
```c
include include define N 200 int main（） { int i, j； for （i = 2； i <= N； i++） { for （j = 2； j <= sqrt（i）； j++） { if （i % j == 0） { break； } } if （j > sqrt（i）） { printf（"%d ", i）； } } return 0； } ``` 2. 埃拉托斯特尼筛法（Sieve of Eratosthenes） 埃拉托斯特尼筛法是一种高效的求质数方法，时间复杂度为O（N log log N）。该方法通过逐步筛选掉合数，最终留下质数。 ```c include include define maxl 200000000 bool a[maxl] = {0}； void sushu（int n） { for （int i = 2； i <= n； i++） { a[i] = true； } for （int i = 2； i * i <= n； i++） { if （a[i]） { for （int j = i * i； j <= n； j += i） { a[j] = false； } } } } int main（） { int n； printf（"请输入范围n:"）； scanf（"%d", &n）； sushu（n）； for （int i = 2； i <= n； i++） { if （a[i]） { printf（"%d ", i）； } } return 0； } ``` 3. 米勒-拉宾素性测试（Miller-Rabin Primality Test） 米勒-拉宾素性测试是一种概率性算法，用于检测一个数是否为质数。虽然它是概率性的，但在实际应用中非常有效，尤其是对于大数的素性测试。 ```c include include include define D 5 define N 1000 bool isPrime（int num） { if （num <= 1） { return false； } if （num == 2 || num == 3） { return true； } if （num % 2 == 0） { return false； } int d = num - 1； while （d % 2 == 0） { d /= 2； } for （int i = 0； i < D； i++） { int a = 2 + rand（） % （num - 4）； int x = pow（a, d） % num； if （x == 1 || x == num - 1） { continue； } while （d != num - 1） { x = （x * x） % num； d *= 2； if （x == 1） { return false； } if （x == num - 1） { break； } } } return true； } int main（） { int num； printf（"请输入一个数： "）； scanf（"%d", &num）； if （isPrime（num）） { printf（"%d 是质数\n", num）； } else { printf（"%d 不是质数\n", num）； } return 0； } ``` 4. 分段筛法（Segmented Sieve） 分段筛法是一种结合了埃拉托斯特尼筛法和线性筛法的优化方法，适用于求大范围内的质数。