C语言：判断一个数是否为素数/质数

素数/质数的概念：一个的自然数，除了1和它自身外，不能被其他自然数整除的数叫素数，否则成为合数。0和1既不是素数也不是合数，最小的素数是2。

方法1：从2到n - 1判断有没有能整除n的数。如果有，则不是素数，否则是素数；

bool is_prime(int n) {if (n < 2) {return false;}int i;for (i = 2; i < n; ++i){if (n%i == 0) {return false;}}return true;}

算法时间复杂度O(n)

方法2：从2算到sqrt(n)

bool is_prime(int n) {if (n < 2) {return false;}int i;for (i = 2; i*i< n; ++i) {if (n%i == 0) {return false;}}return true;}

算法时间复杂度O(n)