找素数用c语言怎么写

我们可以使用“埃氏筛法”来找素数。具体实现步骤如下：

1. 创建一个大小为n+1的布尔数组prime[]，初始值都为true，表示所有数都是素数。
2. 从2开始遍历到sqrt(n)，如果当前的数i是素数，则将i的倍数j（j=i×i,i×(i+1),...,n）标记为非素数，即将prime[j]的值置为false。
3. 遍历结束后，prime[]数组中为true的数即为素数。

下面是代码实现：

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

void findPrimes(int n) {
    bool prime[n+1];    // 布尔数组，表示是否为素数
    memset(prime, true, sizeof(prime));    // 初始化为true

    // 埃氏筛法
    for (int i = 2; i <= sqrt(n); i++) {
        if (prime[i]) {    // 如果i是素数，则将其倍数标记为非素数
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

    // 输出所有素数
    printf("The prime numbers less than or equal to %d are:\n", n);
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            printf("%d ", i);
        }
    }
}

int main() {
    int n;
    printf("Please enter a positive integer: ");
    scanf("%d", &n);
    findPrimes(n);
    return 0;
}

注意：在使用sqrt函数时，需要包含math.h头文件。另外，由于本算法的空间复杂度为O(n)，因此当n较大时，可能会出现内存溢出的问题。