c语言筛选法输出100以内的素数

下面是一种使用筛选法计算 100 以内素数的 C 语言程序：

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

int main() {
  const int max = 100;
  bool isPrime[max+1];
  for (int i = 2; i <= max; i++) {
    isPrime[i] = true;
  }
  for (int i = 2; i * i <= max; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j <= max; j += i) {
        isPrime[j] = false;
      }
    }
  }
  for (int i = 2; i <= max; i++) {
    if (isPrime[i]) {
      printf("%d ", i);
    }
  }
  return 0;
}

程序中的 `isPrime` 数组用于记录某个数字是否为素数，初始化为 `true`。然后从 2 开始，如果它是素数，就把它的倍数都标记为非素数，最后输出所有标记为素数的数字。

这个算法的时间复杂度为 O(nloglogn)，比试除法更优秀。

相关问题

c语言筛选法求200以内素数

以下是使用筛选法求200以内素数的C语言代码：

#include <stdio.h>

int main()
{
    int n = 200;
    int prime[201] = {0}; // 初始化数组，0表示未筛选，1表示合数，2表示素数
    int i, j;

    for (i = 2; i <= n; i++)
    {
        if (prime[i] == 0) // i为素数
        {
            printf("%d ", i);
            for (j = i * i; j <= n; j += i) // 将i的倍数标记为合数
            {
                prime[j] = 1;
            }
            prime[i] = 2; // 标记i为素数
        }
    }

    return 0;
}

该程序使用了一个数组 `prime` 来记录每个数字的状态，初始时所有数字都被标记为未筛选。程序从2开始枚举每个数字，如果该数字未被标记为合数，则输出该数字并将其倍数标记为合数。最后，被标记为素数的数字被标记为2。

c语言筛选法求200以内素数，每行输出五个数，在结果中输出共有几个素数

以下是使用筛选法求200以内素数，并且每行输出五个数的C语言代码：

#include <stdio.h>

int main()
{
    int n = 200;
    int prime[201] = {0}; // 初始化数组，0表示未筛选，1表示合数，2表示素数
    int i, j, count = 0;

    for (i = 2; i <= n; i++)
    {
        if (prime[i] == 0) // i为素数
        {
            printf("%d ", i);
            count++;
            if (count % 5 == 0) // 每行输出五个数
            {
                printf("\n");
            }
            for (j = i * i; j <= n; j += i) // 将i的倍数标记为合数
            {
                prime[j] = 1;
            }
            prime[i] = 2; // 标记i为素数
        }
    }

    printf("\n共有%d个素数\n", count); // 输出素数的个数

    return 0;
}

该程序与上一个程序类似，不同之处在于每输出五个素数就换行，并且在最后输出素数的个数。