素数判断方式,判断是否是素数的算法

目录 定义 算法 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）直