C++判断是否是素数（质数）-蒲公英云

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

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

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

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

在这里插入图片描述
拿64来说，64有因数1，2，4，8，16，32，64

看64的因数是成对出现的

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

抛开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;
}