除了1和自身之外不能整除其它数, 称之为素数. 最小的素数是2. 没有最大的素数.

1000以内素数, 如下图所示:

关于素数的算法, 一般有2种.

第1种, 给出一个数n(n >= 2), 判断n是不是素数

第2种, 给出一个数n(n >= 2), 把[2, n]的所有素数拿出来

判断一个数n是否是素数, 最简单粗暴的方法就是把n分别与i(i的范围是[2, n-1])求余

稍微想一下我们就能知道, 只需判断n与[2, n/2]求余即可

再高级点利用数学上的证明, 可以得出, 只需判断n与[2, sqrt(n)]求余即可

C语言sqrt的原型是: double sqrt(double x)

下面的代码展示了2个利用sqrt(n)就素数的算法, 其中第2个算法通过一些简单的变换, 使

我们不必具体求出sqrt(n)的值, 就能判断n是不是素数

#include 
    
     #include 
     
      int isPrime1 (int n);int isPrime2 (int n);int main () {    int i;    // 打印 [2, 1000]内的所有素数    for (i=2; i<=1000; i++) {        if (isPrime2(i) == 1) {            printf("%6d", i);        }    }    return 0;}// 判断n是否是素数(利用库函数sqrt(n))// 返回值: 是返回1, 否返回0int isPrime1 (int n) {    int i;    int flag = 1; // 先假设n就是素数    int squareRoot = (int)(sqrt(n));    for (i=2; i<=squareRoot; i++) {        if (n % i == 0) {            flag = 0;            break;        }    }    return flag;}// 判断n是否是素数(不使用sqrt())// 返回值: 是返回1, 否返回0int isPrime2 (int n) {    int i = 2;    int flag = 1;    while (i * i <= n) {        if (n % i == 0) {            flag = 0;            break;        }        i++;    }    return flag;}