【C语言必刷题】4. 打印100~200之间的素数

爱敲代码的小杨.

发布于 2024-05-07 19:20:40

670

发布于 2024-05-07 19:20:40

文章被收录于专栏：JavaJava

🔥 题目描述

使用C语言写一个程序打印100~200之间的的素数，数字中间使用空格分割。

🔥 解题思路

素数是指只能被1和它本身整除的正整数。我们可以遍历100~200，并找出那些数字是素数。

试除法：从 2 到 x-1 ，逐个尝试是否能整除 x，如果能，x就不是素数，否则 x 是素数优化代码：当 x 为偶数时，x 一定不是素数，因此在遍历时我们可以跳过每个偶数
试除法时间优化：
- 当 2 到 x-1 中存在某个数 t 可以整除 x 时，令 d = x/t，则 d 也可以整除 x，并且结果为 t。因此，当 2~
\sqrt[]x
中不存在可以整除x的数时，
\sqrt[]x+1
~ x 也不存在可以整除 x 的数。
- 利用反证法证明：
  1. 假设 2 到 x-1 中不存在可以整除 x 的数，
  \sqrt[]x+1
  ~x 中存在⼀个数 d 可以整除 x；
  1. 存在另⼀个数 t=x/d 也可以整除 x；
  2. t*d=x，因为 d＞
  \sqrt[]x
  ，所以 t＜
  \sqrt[]x
  ，即 2 到 x-1 中存在某个数 t 可以整除 x；
  1. 与假设矛盾，反证成成立。

🔥代码

#include <stdio.h>

int main()
{
    int i = 0;
    for (i = 100; i <= 200; i++) // 遍历100到200之间的每个数
    {
        int flg = 1; // flg用于标记是否为素数，初始假设为素数
        int j = 0;
        for (j = 2; j < i; j++) // 遍历2到i-1之间的每个数
        {
            if (i % j == 0) // 若i能被j整除，则i不是素数
            {
                flg = 0; // 修改flg标记为0，表示i不是素数
                break;    // 退出内层循环，无需继续判断
            }
        }

        if (flg != 0) // 若flg为1，表示i是素数
        {
            printf("%d ", i); // 输出素数i
        }
    }

    return 0;
}

// 优化1
#include <stdio.h>

int main()
{
    int i = 0;
    for (i = 101; i <= 200; i += 2) // 从101开始，每次增加2，遍历101到200之间的每个奇数
    {
        int flg = 1; // flg用于标记是否为素数，初始假设为素数
        int j = 0;
        for (j = 2; j < i; j++) // 遍历2到i-1之间的每个数
        {
            if (i % j == 0) // 若i能被j整除，则i不是素数
            {
                flg = 0; // 修改flg标记为0，表示i不是素数
                break;    // 退出内层循环，无需继续判断
            }
        }

        if (flg != 0) // 若flg为1，表示i是素数
        {
            printf("%d ", i); // 输出素数i
        }
    }

    return 0;
}

// 优化2
#include <stdio.h>
#include <math.h>

int main()
{
    int i = 0;
    for (i = 101; i <= 200; i += 2) // 从101开始，每次增加2，遍历101到200之间的每个奇数
    {
        int flg = 1; // flg用于标记是否为素数，初始假设为素数
        int j = 0;
        for (j = 2; j <= sqrt(i); j++) // 遍历2到sqrt(i)之间的每个数
        {
            if (i % j == 0) // 若i能被j整除，则i不是素数
            {
                flg = 0; // 修改flg标记为0，表示i不是素数
                break;    // 退出内层循环，无需继续判断
            }
        }

        if (flg != 0) // 若flg为1，表示i是素数
        {
            printf("%d ", i); // 输出素数i
        }
    }

    return 0;
}

运行结果：