C语言如何筛求素数

创作时间:

作者:

@小白创作中心

C语言如何筛求素数

引用

来源

https://docs.pingcode.com/baike/976679

本文将介绍C语言中筛选素数的几种方法，包括埃拉托斯特尼筛法、直接判断法和分块筛法。这些方法各有优劣，适用于不同的场景。通过本文，你将能够理解并实现这些算法，从而在实际项目中选择合适的方法来筛选素数。

C语言筛选素数的方法有多种，主要包括：直接判断法、埃拉托斯特尼筛法（Sieve of Eratosthenes）和分块筛法。其中，埃拉托斯特尼筛法是一种经典且效率较高的方法，适合处理较大范围的素数筛选。本文将详细介绍埃拉托斯特尼筛法的原理、实现步骤及代码示例，同时也会探讨其他筛选方法的优缺点。

一、埃拉托斯特尼筛法

1、原理介绍

埃拉托斯特尼筛法是一种古老但非常高效的算法，其核心思想是通过标记合数来排除非素数，最终筛选出所有的素数。具体步骤如下：

创建一个长度为n+1的布尔数组isPrime，初始时所有元素设置为true。
从2开始，遍历数组，如果当前元素isPrime[i]为true，则将其所有倍数标记为false。
遍历完成后，数组中仍为true的索引即为素数。

2、代码示例

以下是用C语言实现埃拉托斯特尼筛法的代码示例：

#include <stdio.h>
#include <stdlib.h>  
#include <stdbool.h>  

// 埃拉托斯特尼筛法  
void sieveOfEratosthenes(int n) {  
    // 创建布尔数组并初始化  
    bool *isPrime = (bool*)malloc((n+1) * sizeof(bool));  
    for (int i = 0; i <= n; i++) {  
        isPrime[i] = true;  
    }  

    // 从2开始筛选  
    for (int p = 2; p * p <= n; p++) {  
        // 如果isPrime[p]为true，则标记其所有倍数  
        if (isPrime[p] == true) {  
            for (int i = p * p; i <= n; i += p) {  
                isPrime[i] = false;  
            }  
        }  
    }  

    // 输出所有素数  
    for (int p = 2; p <= n; p++) {  
        if (isPrime[p]) {  
            printf("%d ", p);  
        }  
    }  
    printf("\n");  

    // 释放内存  
    free(isPrime);  
}  

int main() {  
    int n;  
    printf("请输入一个正整数：");  
    scanf("%d", &n);  
    printf("小于等于%d的所有素数为：\n", n);  
    sieveOfEratosthenes(n);  
    return 0;  
}

3、详细描述

初始化布尔数组：首先，创建一个长度为n+1的布尔数组isPrime，并将所有元素初始化为true。这表示默认假设所有数都是素数。

筛选过程：从2开始，遍历数组。如果isPrime[i]为true，则将i的所有倍数标记为false。为了优化，内层循环从p*p开始，因为比p*p小的倍数在之前的步骤中已经被标记过了。

输出结果：遍历数组，将所有为true的索引值输出，这些索引值就是素数。

二、直接判断法

1、原理介绍

直接判断法是一种简单但效率较低的方法，其核心思想是逐个判断每个数是否为素数。具体步骤如下：

对于每个数n，判断是否存在小于n的因数。
如果存在，则n不是素数；如果不存在，则n是素数。

2、代码示例

以下是用C语言实现直接判断法的代码示例：

#include <stdio.h>
#include <stdbool.h>  

// 判断是否为素数  
bool isPrime(int n) {  
    if (n <= 1) return false;  
    for (int i = 2; i * i <= n; i++) {  
        if (n % i == 0) return false;  
    }  
    return true;  
}  

// 打印所有小于等于n的素数  
void printPrimes(int n) {  
    for (int i = 2; i <= n; i++) {  
        if (isPrime(i)) {  
            printf("%d ", i);  
        }  
    }  
    printf("\n");  
}  

int main() {  
    int n;  
    printf("请输入一个正整数：");  
    scanf("%d", &n);  
    printf("小于等于%d的所有素数为：\n", n);  
    printPrimes(n);  
    return 0;  
}

3、详细描述

判断素数：通过一个辅助函数isPrime，判断一个数是否为素数。如果一个数n小于等于1，则它不是素数。对于大于1的数，通过遍历其所有小于等于sqrt(n)的因数，判断是否存在整除。

输出结果：遍历范围内的所有数，通过isPrime函数判断是否为素数，是则输出。

三、分块筛法

1、原理介绍

分块筛法是对埃拉托斯特尼筛法的优化，适用于非常大的数范围。其核心思想是将范围分块，每次处理一块数据，从而减少空间复杂度和内存占用。

2、代码示例

以下是用C语言实现分块筛法的代码示例：

#include <stdio.h>
#include <stdlib.h>  
#include <stdbool.h>  
#include <math.h>  

// 分块筛法  
void segmentedSieve(int n) {  
    int limit = floor(sqrt(n)) + 1;  
    bool *isPrime = (bool*)malloc((limit + 1) * sizeof(bool));  
    for (int i = 0; i <= limit; i++) {  
        isPrime[i] = true;  
    }  

    for (int p = 2; p * p <= limit; p++) {  
        if (isPrime[p]) {  
            for (int i = p * p; i <= limit; i += p) {  
                isPrime[i] = false;  
            }  
        }  
    }  

    int low = limit;  
    int high = 2 * limit;  
    while (low < n) {  
        if (high >= n) {  
            high = n + 1;  
        }  

        bool *mark = (bool*)malloc((high - low + 1) * sizeof(bool));  
        for (int i = 0; i < high - low + 1; i++) {  
            mark[i] = true;  
        }  

        for (int i = 2; i <= limit; i++) {  
            if (isPrime[i]) {  
                int loLim = floor(low / i) * i;  
                if (loLim < low) {  
                    loLim += i;  
                }  

                for (int j = loLim; j < high; j += i) {  
                    mark[j - low] = false;  
                }  
            }  
        }  

        for (int i = low; i < high; i++) {  
            if (mark[i - low]) {  
                printf("%d ", i);  
            }  
        }  

        low = low + limit;  
        high = high + limit;  
        free(mark);  
    }  

    free(isPrime);  
    printf("\n");  
}  

int main() {  
    int n;  
    printf("请输入一个正整数：");  
    scanf("%d", &n);  
    printf("小于等于%d的所有素数为：\n", n);  
    segmentedSieve(n);  
    return 0;  
}