目录

定义 算法 1）直观判断法 2）直观判断法改进（2种） 3）已知最快的算法 实现 C python

定义

约数只有1和本身的整数称为质数，或称素数。 计算机或者相关专业，基本上大一新生开始学编程都会接触的一个问题就是判断质数，下面分享几个判断方法，从普通到高效。

算法

1）直观判断法

最直观的方法，根据定义，因为质数除了1和本身之外没有其他约数，所以判断n是否为质数，根据定义直接判断从2到n-1是否存在n的约数即可。C 代码如下：

bool isPrime_1(int n){ for(int i=2;i<n;i ) if(n%i==0&&i<n) return 0; //注意2是质数 return 1; }

显然时间复杂度为o(n)。

2）直