C语言练习题-C语言练习题实例33

题目：判断一个数字是否为质数（素数）。

程序分析：质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。

实例

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

#define MAX 1000

int prime[MAX];

int isPrimeNaive(int n) {
    if (n <= 1)
        return 0;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return 0;

    return 1;
}

int isPrime(int n) {
    if (n <= 1)
        return 0;

    if (n == 2)
        return 1;

    if (n % 2 == 0)
        return 0;

    int limit = (int)sqrt((double)n);

    for (int i = 3; i <= limit; i = i + 2) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

void sieve() {
    prime[0] = 0;
    prime[1] = 0;

    for (int i = 2; i < MAX; i++)
        prime[i] = 1;

    int limit = (int)sqrt((double)MAX);

    for (int i = 2; i <= limit; i++) {
        if (prime[i])
            for (int j = i * i; j <= MAX; j += i)
                prime[j] = 0;
    }
}

int isPrimeSieve(int n) {
    if (prime[n])
        return 1;
    else
        return 0;
}

int main() {
    sieve();

    printf("N=%d %d\n", 1, isPrime(1));
    printf("N=%d %d\n", 2, isPrime(2));
    printf("N=%d %d\n", 3, isPrime(3));
    printf("N=%d %d\n", 4, isPrime(4));
    printf("N=%d %d\n", 7, isPrime(7));
    printf("N=%d %d\n", 9, isPrime(9));
    printf("N=%d %d\n", 13, isPrime(13));
    printf("N=%d %d\n", 17, isPrime(17));
    printf("N=%d %d\n", 100, isPrime(100));
    printf("N=%d %d\n", 23, isPrime(23));
    printf("N=%d %d\n", 1, isPrime(1));

    return 0;
}

以上实例输出结果为（末尾数字 1 表示是质数，0 表示不是质数）：

N=1 0
N=2 1
N=3 1
N=4 0
N=7 1
N=9 0
N=13 1
N=17 1
N=100 0
N=23 1
N=1 0

该程序中定义了几个函数来判断一个数字是否为质数。函数 isPrimeNaive 是最简单的方法，通过从 2 到 n-1 遍历判断是否有因数，但效率较低。函数 isPrime 使用了更高效的方法，从 2 开始遍历到 sqrt(n)，并检查是否有因数。函数 sieve 是使用筛法（埃拉托斯特尼筛法）生成小于等于 MAX 的所有质数，并存储在数组 prime 中。函数 isPrimeSieve 使用筛法生成的质数数组来判断一个数字是否为质数。

在主函数中，我们调用这些函数来判断一些数字是否为质数，并输出结果。