c 语言求素数方法:暴力法:逐一检查每个数是否满足素数条件。埃拉托斯特尼筛法:创建一个数表,逐一筛除合数。miller-rabin 测试:使用费马小定理和欧拉准则判断素数。
如何用 C 语言求素数
素数,又称质数,是指大于 1 且只能被 1 和自身整除的自然数。用 C 语言求素数,主要有以下方法:
1. 暴力法
这种方法最简单,通过逐一检查每个数是否满足素数条件,来判断其是否为素数。实现代码如下:
#include <stdio.h>
int isPrime(int num) {
if (num <p><strong>2. 埃拉托斯特尼筛法</strong></p>
<p>这种方法通过创建一张数表,并逐一筛除合数(非素数),来找出素数。实现代码如下:</p>
<pre class="brush:php;toolbar:false">#include <stdio.h>
#include <stdlib.h>
int main() {
int SIZE = 100; // 保存整数的数表大小
int *arr = (int *)malloc(SIZE * sizeof(int));
// 初始化数表,所有数都认为是素数
for (int i = 0; i <p><strong>3. Miller-Rabin 测试</strong></p>
<p>这种方法通过使用费马小定理和欧拉准则,在一定概率下判断一个数是否为素数。实现代码较复杂,这里不再给出。</p></stdlib.h></stdio.h>