C语言素数怎么算-C++-PHP中文网

C语言素数怎么算

下次还敢

发布： 2024-05-26 04:09:21

原创

1251人浏览过

C 语言中计算素数的方法有三种：遍历法、埃拉托斯特尼筛法和费马小定理。遍历法逐个遍历整数，检查是否仅被 1 和自身整除。埃拉托斯特尼筛法用布尔数组标记素数，将非素数倍数标记为非素数。费马小定理基于数学定理，通过检验随机整数的指数运算结果来判断素数。

C语言素数怎么算

C语言中计算素数的方法

素数定义：
素数是指仅被 1 和自身整除的正整数（不包含 1）。

C语言中计算素数的方法：

方法 1：遍历法

OpenMP并行程序设计 WORD版

本文档主要讲述的是OpenMP并行程序设计；OpenMP是一个编译器指令和库函数的集合，主要是为共享式存储计算机上的并行程序设计使用的。目前支持OpenMP的语言主要有Fortran，C/C++。 OpenMP在并行执行程序时，采用的是fork/join式并行模式，共享存储式并行程序就是使用fork/join式并行的。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看

查看详情

立即学习“C语言免费学习笔记（深入）”；

从 2 开始逐个遍历每个整数。
对于每个整数 n，检查它是否满足以下条件：

<code class="c">bool isPrime = true;
for (int i = 2; i <= n/2; i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
if (isPrime) {
    // n 是素数
}</code>

登录后复制

方法 2：埃拉托斯特尼筛法

创建一个布尔数组，其中第 n 个元素表示数字 n 是否是素数。
从 2 开始，逐个遍历每个整数 n。
将数组中 n 的倍数标记为非素数。
在遍历结束后，数组中标记为素数的元素表示素数。

<code class="c">#include <stdbool.h>

bool isPrime[N+1];

void sieveOfEratosthenes() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
    }
}</code>

登录后复制

方法 3：费马小定理

对于任意整数 a 和正整数 p，如果 a 不是 p 的倍数，则 a^(p-1) ≡ 1 (mod p)。
如果 a^(p-1) ≡ 1 (mod p) 成立，则 p 是素数。

<code class="c">bool isPrimeFermat(int n, int k) {
    if (n <= 1) {
        return false;
    }
    for (int i = 0; i < k; i++) {
        int a = rand() % (n-1) + 1;
        if (pow(a, n-1, n) != 1) {
            return false;
        }
    }
    return true;
}</code>

登录后复制

以上就是C语言素数怎么算的详细内容，更多请关注php中文网其它相关文章！