C语言经典例12-判断素数最简单的方法

痛定思痛。 2023-07-03 04:49 7阅读 0赞

### 目录 ###

*  1 题目
 *  2 分析
 *  3 实现
 *   *  3.1 实现1（常规暴力方法，效率低）
     *  3.2 实现2（稍微优化）
     *  3.3 实现3（最终优化，这个方法推荐记下来）
 *  4 运行结果

# 1 题目 #

判断并输出101到200之间的素数

> 注：想节约时间的可以直接看实现3

# 2 分析 #

本题的关键是输出素数，素数又叫质数，指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，必须为正整数，1和0既非素数也非合数，所以在写判断素数的函数时

*  第一步首先判断给的数是否大于2，若小于2，则直接判断为非素数，
 *  第二步则用一个`for`循环来对小于该数的各个数依次取余，若取余后等于0，则它不是素数，那么容易得出`实现1`，仔细想想可以发现，一个数去除以比它的一半还要大的数，一定是除不尽的，这用不着判断，所以要改进`for`循环中的循环控制语句，改为`i < n/2 + 1`，见`实现2`

那么还可以再优化吗？答案是可以的，在数学上有个规律，对于一个小于`n`的整数`x`，若`n`不能整除`x`，则`n`必定不能整数`n/x`，那么带来一个明显的优化就是循环控制语句从`2`到 n \\sqrt\{n\} n即可，因为在判断2的同时也判断了`n/2`，循环到 n \\sqrt\{n\} n时，就把`2`到`n-1`都判断了，所以要改进`for`循环中的循环控制语句，改为`i <= sqrt(n)`，见`实现3`。

# 3 实现 #

## 3.1 实现1（常规暴力方法，效率低） ##

int isPrime(int n) { 
        if (n < 2) { 
            return 0; // 0和1非素数，直接判断
        }
        for (int i = 2; i < n; i++) { 
            if (n % i == 0) { 
                return 0; // 依次取余，若除的尽，则不是素数
            }
        }
        return 1;
    }

## 3.2 实现2（稍微优化） ##

int isPrime(int n) { 
        if (n < 2) { 
            return 0; // 0和1非素数，直接判断
        }
        for (int i = 2; i < n/2 + 1; i++) { 
            if (n % i == 0) { 
                return 0; // 依次取余，若除的尽，则不是素数
            }
        }
        return 1;
    }

## 3.3 实现3（最终优化，这个方法推荐记下来） ##

#include <stdio.h>
    #include <math.h>
    
    int isPrime(int n) { 
        if (n < 2) { 
            return 0;
        }
        for (int i = 2; i <= sqrt(n); i++) { 
            if(n % i == 0) { 
                return 0;
    	    }
        }
        return 1;
    }
    
    int main() { 
        for (int i = 101; i <= 200; i++) { 
            if (isPrime(i)) { 
                printf("%d\n", i);
            }
        }
        return 0;
    }

# 4 运行结果 #

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