C++判断是否是素数（质数）

傷城~ 2023-02-27 03:23 27阅读 0赞

素数就是除1和它本身外没有其他的因数了叫做素数  
1只有1个因数1，所有1既不是合数也不是素数  
4有3个因数，属于合数  
2只有2个因数，属于质数或素数

### 那么怎么判断一个数是素质数呢 ###

![在这里插入图片描述][2020071611124867.png_pic_center]  
拿64来说，64有因数1，2，4，8，16，32，64

### 看64的因数是成对出现的 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]  
结论：任何一个合数它的因数都是成对出现的  
**那么是素数怎么判断**  
为了让程序更加整洁，快速，我们不妨可以这样想  
**一个数如果它的一半还没有因数，那么这个数就是质数**

### 抛开1和它本身，把除数定为2 ###

我们第一次判断这个数时，把初始的除数定为2  
3%2=1，不能整除  
此时2已经是3的一半多了，所以3是质数

--------------------

17%2=1，不能整除  
将除数+1为3  
17%3=2，不能整除  
将除数+1为4  
17%4=1，不能整除  
。  
。  
。  
一直到  
17%9=8，不能整除  
此时9已经大于了17的一半，所以17是质数

### 更加整洁使用开平方sqrt ###

我们已经会判断是不是质数了，但是为了更加整洁  
**将大于n的一半改为大于开n的平方**  
64的平方根是8，那么8的前面已经有因数2，4了  
9的平方根是3，那么3正好是9的因数  
可见，这样的算法更加整洁，快速

### 源码 ###

#include<iostream>
    #include<cmath>//开平方必须加入头文件
    using namespace std;
    bool op(int n,int m)//判断素数，n为判断的数，m为除数，初始值为2
    { 
        if(m>sqrt(n)) return true;//如果搜到了它的开平方还没有因数，判断这个数一定是素数，返回值为true
        if(n%m==0) return false;//如果可以被整除则不是素数，返回值为false
        op(n,m++);//递归，每次让除数m+1
    }
    int main()
    { 
        int n;
        cin>>n;//输入一个数
        if(op(n,2))//如果返回值为true
        { 
            cout<<n<<"为一个素数";//输出n为一个素数
        }
        else//如果返回值为false
        { 
            cout<<n<<"不为一个素数";//输出n不为一个素数
        }
        return 0;
    }

[2020071611124867.png_pic_center]: /images/20230209/bce1bff34db34eccb823f00febdd8316.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/984f4172da1f43ddbb99a6e30a2fa0d9.png