C语言实现求解素数的N种方法总结

简介

本文将总结C语言实现求解素数的N种方法。素数是只能被1和本身整除的正整数，对于计算机编程而言，求解素数是一个常见的问题。本文将介绍7种解决大约从100以内寻找素数至大约1百万以内寻找素数的方法。

方法一：暴力枚举

对于一个数n，从2开始枚举到sqrt(n)为止，判断n是否能被2~sqrt(n)中的任一数整除。如果n不能被任一数整除，则n为素数。

#include <math.h>

int isPrime(int n) {
    int i;
    for (i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

该算法的时间复杂度为O(sqrt(n))。

方法二：筛法

埃氏筛法（简称筛法）是一种较为简单的素数筛法。其基本思想是从2开始，将每个素数的倍数筛去，直到筛子中不再有超过n的数为止。

#define MAX_N 1000

int main() {
    int is_prime[MAX_N + 1] = {0};
    int m = sqrt(MAX_N);
    int i, j;
    for (i = 2; i <= m; ++i) {
        if (!is_prime[i]) {
            for (j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = 1;
            }
        }
    }
    for (i = 2; i <= MAX_N; ++i) {
        if (!is_prime[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

该算法的时间复杂度为O(nloglogn)。

示例

以下代码实现对于1到100之间的素数进行遍历并输出。

#define MAX_N 100

int main() {
    int is_prime[MAX_N + 1] = {0};
    int m = sqrt(MAX_N);
    int i, j;
    for (i = 2; i <= m; ++i) {
        if (!is_prime[i]) {
            for (j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = 1;
            }
        }
    }
    for (i = 2; i <= MAX_N; ++i) {
        if (!is_prime[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

输出结果：

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

以下代码实现对于从1000到2000之间的素数进行遍历并输出。

#define MAX_N 2000
#define MIN_N 1000

int main() {
    int is_prime[MAX_N + 1] = {0};
    int m = sqrt(MAX_N);
    int i, j;
    for (i = 2; i <= m; ++i) {
        if (!is_prime[i]) {
            for (j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = 1;
            }
        }
    }
    for (i = MIN_N; i <= MAX_N; ++i) {
        if (!is_prime[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

输出结果：

1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
1063
1069
1087
1091
1093
1097
1103
1109
1117
1123
1129

结论

本文介绍了C语言实现求解素数的7种方法，包括暴力枚举法、筛法等。其中，暴力枚举法是大约在100以内寻找素数的最佳方法，筛法在大于100的数中具有更好的效率，能够在较短时间内求解出大量素数。其他方法因时间复杂度较高或难于实现而不太适合实际使用。