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

📚博客主页：爱敲代码的小杨.

✨专栏：《Java SE语法》 | 《数据结构与算法》 | 《C生万物》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

文章目录

• 🔥 题目描述
• 🔥 解题思路
• 🔥代码

  🔥 题目描述

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

  🔥 解题思路

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

  1. 试除法：从 2 到 x-1 ，逐个尝试是否能整除 x，如果能，x就不是素数，否则 x 是素数

     优化代码：当 x 为偶数时，x 一定不是素数，因此在遍历时我们可以跳过每个偶数

  2. 试除法时间优化：

     • 当 2 到 x-1 中存在某个数 t 可以整除 x 时，令 d = x/t，则 d 也可以整除 x，并且结果为 t。因

       
       （图片来源网络，侵删）

       此，当 2~ x \sqrt[]x x ​中不存在可以整除x的数时， x + 1 \sqrt[]x+1 x ​+1​~ x 也不存在可以整除 x 的数。

     • 利用反证法证明：

       1. 假设 2 到 x-1 中不存在可以整除 x 的数， x + 1 \sqrt[]x+1 x ​+1~x 中存在⼀个数 d 可以整除 x；

       2. 存在另⼀个数 t=x/d 也可以整除 x；

       3. t*d=x，因为 d＞ x \sqrt[]x x ​ ，所以 t＜ x \sqrt[]x x ​，即 2 到 x-1 中存在某个数 t 可以整除 x；

       4. 与假设矛盾，反证成成立。

  🔥代码

  #include 
  int main()
  {
      int i = 0;
      for (i = 100; i 
          int flg = 1; // flg用于标记是否为素数，初始假设为素数
          int j = 0;
          for (j = 2; j