素数c语言程序编写

C语言实现素数检测程序

在计算机科学中，素数是一个非常重要的概念，素数是只有两个正因数（1和它本身）的自然数，也被称为质数，2，3，5，7，11，13，17，19，23，29等都是素数，在许多数学问题和算法中，素数都有着重要的应用，编写一个能够检测素数的C语言程序是非常有意义的。

我们需要了解如何判断一个数是否为素数，一种简单的方法是试除法，即从2开始，到这个数的平方根结束，看这个数能否被其中任何一个数整除，如果能被整除，那么这个数就不是素数；如果不能被整除，那么这个数就是素数，这种方法虽然简单，但是效率较低，特别是对于较大的数。

另一种方法是埃拉托斯特尼筛选法，也称为素数筛，这种方法的基本思想是先假设所有的数都是素数，然后从2开始，去掉2的倍数，然后去掉3的倍数，然后去掉4的倍数，以此类推，直到去掉所有小于或等于这个数的平方根的倍数，剩下的就是素数，这种方法的效率较高，特别是对于较大的数。

下面是一个使用埃拉托斯特尼筛选法实现的C语言程序：

#include <stdio.h>
#include <math.h>
#define MAX 1000000
int prime[MAX+1];
void sieve() {
    int i, j;
    for(i = 2; i <= sqrt(MAX); i++) {
        if(prime[i] == 0) {
            for(j = i*i; j <= MAX; j += i) {
                prime[j] = 1;
            }
        }
    }
}
int main() {
    int n, i, flag;
    sieve();
    scanf("%d", &n);
    flag = prime[n];
    if(flag == 0) {
        printf("%d is a prime number.
", n);
    } else {
        printf("%d is not a prime number.
", n);
    }
    return 0;
}

在这个程序中，我们首先定义了一个数组prime[]，用于存储每个数是否为素数，我们定义了一个函数sieve()，用于实现埃拉托斯特尼筛选法，在main()函数中，我们首先调用sieve()函数生成素数表，然后读取用户输入的数n，最后根据素数表判断n是否为素数。