目录

  • 摘要
  • 方法1
    • 素数是什么
    • 条件分析
    • 设计思路
      • 大体思路
    • 具体代码实现
    • 代码优化
  • 方法2
      • 注意：判断最终的b是否等于a
  • 方法3
      • PS：思路不变，形式变化
  • 小结

摘要

本文介绍了判断素数的3种方法，从素数的概念分析，确定找到素数的几个必要条件，设计思路，并将代码进行优化。此外，还使用自定义函数的形式将同样的思路进行实现。

方法1

素数是什么

素数，就是仅能被自身和1整除的数字。

条件分析

首先我们可以提取出判断素数的三个基本条件：

  1. 素数是整数
  2. 素数能被自身整除
  3. 素数能被1整除

设计思路

以一道题为例——
求100到200之间的所有素数并输出。

大体思路

  • 遍历
    • 首先，得到100到200间的所有数字（记为a）——for循环
    • 当 A%B==0时说明A被B整除了
    • 根据两个基本条件——a能被1整除，且a能被自身整除，所以除数（记为b）应为2到a-1间的所有数字——for循环
  • 设置判断条件
    • 当a%b==0时a不是素数
    • 设置标记变量flag，当a%b==0时令flag=1；后续循环没必要进行，因此设置break；结束该循环。
    • 特别注意flag何时初始化为0

具体代码实现

#includeint main(){int a, b, flag;for (a = 100; a <= 200; a++)//得到100到200间的所有数字{flag = 0; //先假设a为素数 for (b = 2; b < a; b++) //注意，不要忘了自身也能被整除！{if (a % b == 0){flag = 1;//若出现不能整除的情况，则令flag为1 break;}}//标记变量——flagif (0 == flag)printf("%d ", a);}return 0;}

最终结果输出为——

101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

代码优化

我们先解决一个数学问题——

若a为一个整数，则显然a=√a√a，因为√a=√a，所以若有其他数cd=a，则一定存在一个数大于√a，一个数小于√a，因此大于√a之后的数字我们不需要再进行遍历了。
（同理，如果你不想思考这么多，写个b<n/2也比全部遍历好多了）

因此第二个循环：

for (b = 2; b < a; b++)

我们可以优化为——

int k;k=(int)sqrt((double)a);for (b = 2; b < a; b++)

注：求平方根函数内参数要求为double类型，因此先将a强制转换为double型，而k是整型，所以将sqrt计算返回值再进行强制转换为int型。

或者用不那么绕的写法——

int k;k=(int)sqrt(1.0*a);//1.0*a同样将a强制转换为double型for (b = 2; b < a; b++)

所以优化之后的代码为——

#include#include//sqrt在math.h头文件中int main(){int a, b, flag;for (a = 100; a <= 200; a++)//得到100到200间的所有数字{flag = 0; //先假设a为素数 int k;k = (int)sqrt((double)i);for (b = 2; b < k; b++) //注意，不要忘了自身也能被整除！{if (a % b == 0){flag = 1;//若出现不能整除的情况，则令flag为1 break;}}//标记变量——flagif (0 == flag)printf("%d ", a);}return 0;}

方法2

我在网上还看到一种思路——
大体与法1（未优化版）一致，但是没有用标记变量flag，而是判断最终b是否等于a——

#includeint main(){int a, b;for (a = 100; a <= 200; a++){for (b = 2; b < a; b++){if (a % b == 0)break;}if (b == a)//反正要全部遍历一遍，不如把代码写得短一点~printf("%d ", a);}return 0;}

注意：判断最终的b是否等于a

这里为何判断的是b等于a而非b等于a-1呢？

例如：当a=101时，进入第二个for循环，进行大量遍历后来到b=100，此时经过if判断同样不满足条件，不进入if语句。
然后就要b++，得到b=101，那么b=101时不满足b，直接进入判断if（b= =a）语句，此时b与a相等。
走到这一步，说明a除了自身与1外没有能被a整除的除数，因此a为素数。

简言之，条件表达式的执行次数总是比循环体的执行次数多一次。

个人认为此方法不如标记函数思路简洁，不过仍不失为一种独特的思路。

方法3

PS：思路不变，形式变化

我们可以将给定一个数字a，判断其是否为素数的这段逻辑封装在一个自定义函数中。
以下是代码实现——

#includeint fun(int a);int main(){int a,ret;for (a = 100; a <= 200; a++)//得到100到200间的所有数字{ ret=fun(a); //ret为返回值，通过判断ret的值确定a是否为素数if(ret==0)printf("%d ",a);}return 0;}int fun(int a){int b;for (b = 2; b < a; b++){if (a % b == 0)return 1;//若能被整除，则返回值为1,结束 }return 0;//若不能被整除，则返回值为0，结束 }

注意 return 1; 和 return 0; 的位置。

小结

  1. 判断素数起码有三种方法
  2. 特别注意标记函数的使用，灵活运行用自定义函数，注意分析for循环的逻辑顺序，注意break;使用的位置，注意sqrt函数的参量类型及头文件，注意简化遍历次数、优化方案的思路。
  3. 希望大家有所收获！