埃拉托斯特尼筛法与欧拉筛法找出一定范围内质数

时间：2024-10-12 09:46:09

一、基本原理


  1. 首先列出从 2 开始的连续自然数序列，一直到指定的上限 n。
  • 例如，要找出小于等于 100 的质数，就列出 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100。
  1. 从序列中的第一个数（即 2）开始，它是质数，然后将其所有的倍数都标记为非质数。
  • 2 的倍数有 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100，将这些数标记为非质数。
  • 现在的序列变为：2, 3, x, 5, x, 7, x, 9, x, 11, x, 13, x, 15, x, 17, x, 19, x, 21, x, 23, x, 25, x, 27, x, 29, x, 31, x, 33, x, 35, x, 37, x, 39, x, 41, x, 43, x, 45, x, 47, x, 49, x, 51, x, 53, x, 55, x, 57, x, 59, x, 61, x, 63, x, 65, x, 67, x, 69, x, 71, x, 73, x, 75, x, 77, x, 79, x, 81, x, 83, x, 85, x, 87, x, 89, x, 91, x, 93, x, 95, x, 97, x, 99, x（其中 x 表示非质数）。
  1. 接着找到下一个未被标记的数，这个数一定是质数，重复步骤 2，直到所有小于等于 sqrt(n) 的质数的倍数都被标记完。
  • 下一个未被标记的数是 3，3 是质数，将 3 的所有倍数（9、12、15……99）标记为非质数。
  • 序列变为：2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, x, 17, x, 19, x, x, x, 23, x, x, x, x, x, 29, x, 31, x, x, x, 37, x, 41, x, x, x, 43, x, x, x, x, x, 47, x, 49, x, x, x, 53, x, x, x, x, x, 59, x, 61, x, x, x, 67, x, x, x, x, x, 71, x, 73, x, x, x, 77, x, x, x, x, x, 83, x, 89, x, x, x, 97, x, x, x。
  • 继续这个过程，找到下一个未被标记的数 5，5 是质数，将 5 的所有倍数（25、30、35……100）标记为非质数。
  • 序列变为：2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, x, 17, x, 19, x, x, x, 23, x, x, x, x, x, 29, x, 31, x, x, x, 37, x, 41, x, x, x, 43, x, x, x, x, x, 47, x, x, x, x, x, 53, x, x, x, x, x, 59, x, 61, x, x, x, 67, x, x, x, x, x, 71, x, 73, x, x, x, 77, x, x, x, x, x, 83, x, 89, x, x, x, 97, x, x, x。
  1. 最后剩下的未被标记的数就是质数。
  • 在这个例子中，最后剩下的未被标记的数就是小于等于 100 的所有质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。


二、原理分析


  1. 为什么从 2 开始筛除倍数就能找出质数呢？
  • 因为一个合数一定可以分解成若干个质数的乘积。如果一个数不是质数，那么它一定有一个小于等于它的平方根的质因数。所以，当我们从 2 开始筛除倍数时，实际上是在筛除所有含有 2 这个质因数的合数。同理，筛除 3 的倍数就是在筛除所有含有 3 这个质因数的合数，以此类推。
  1. 为什么只需要筛到小于等于 sqrt(n) 的质数呢？
  • 假设一个合数 m，它有两个大于 sqrt(n) 的质因数 p 和 q，那么 m = p * q > sqrt(n) * sqrt(n) = n，这与 m 小于等于 n 矛盾。所以，一个合数至少有一个小于等于它的平方根的质因数。因此，只需要筛到小于等于 sqrt(n) 的质数就可以找出所有小于等于 n 的质数。

以下是用 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;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for (int p = 2; p * p <= n; p++)
    {
        if (isPrime[p]) 
        {
            for (int i = p * p; i <= n; i += p)
            {
                isPrime[i] = false;
            }
        }
    }
    printf("Prime numbers up to %d are: ", n);
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i]) 
        {
            printf("%d ", i);
        }
    }
    free(isPrime);
}

int main()
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    sieveOfEratosthenes(n);
    return 0;
}


这段代码首先动态分配一个布尔类型的数组来标记每个数是否为质数。然后从 2 开始，将每个质数的倍数标记为非质数，直到所有小于等于 sqrt(n) 的质数的倍数都被标记完。最后输出小于等于输入数字 n 的所有质数。

下面介绍欧拉筛法（也叫线性筛法）

除了前面提到的埃拉托斯特尼筛法外，还有一种更高效的质数筛法叫欧拉筛法（线性筛法）。


一、算法原理


  1. 从 2 开始遍历到 n：
  • 对于每个数 i，如果它没有被标记为非质数，那么它就是质数，将其加入质数列表中。
  • 遍历所有小于等于 i 的质数 p，将 p * i 标记为非质数。但这里有一个关键步骤，当 i % p == 0 时停止遍历质数列表，因为此时 p 是 i 的最小质因数，如果继续遍历，会出现重复标记。
  1. 通过这种方式，每个合数只会被它的最小质因数筛掉一次，保证了时间复杂度为线性的 。


二、代码实现（C 语言）

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

void primeSieve(int n)
{
    bool *isPrime = (bool *)malloc((n + 1) * sizeof(bool));
    for (int i = 0; i <= n; i++)
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    int *primes = (int *)malloc(n * sizeof(int));
    int primeCount = 0;
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i])
        {
            primes[primeCount++] = i;
        }
        for (int j = 0; j < primeCount && i * primes[j] <= n; j++) 
        {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
    printf("Prime numbers up to %d are: ", n);
    for (int i = 0; i < primeCount; i++)
    {
        printf("%d ", primes[i]);
    }
    free(isPrime);
    free(primes);
}

int main()
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    primeSieve(n);
    return 0;
}


这个程序首先动态分配一个布尔类型的数组来标记每个数是否为质数，以及一个整数数组来存储找到的质数。然后从 2 开始遍历到 n，对于每个数 i，判断它是否为质数，如果是质数就加入质数列表中。接着，对于每个质数 p，将 p * i 标记为非质数，但当 i % p == 0（即i==p） 时停止，确保每个合数只被筛一次。最后输出小于等于输入数字 n 的所有质数。

相关文章