素数的判断

素数的判断

素数的简介

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

方法一：暴力枚举

思路分析

假如说我们需要知道一个数$ x $是否为一个素数，那么我们可以通过枚举从$ 2 $到$ n-1 $的每一个数，看它是否是$ x $的因子（即通过取模运算判断是否为零）。

时间复杂度O(n)

代码实现

bool isPrime(int x)
{
    bool ans = true;
    for(int i = 2;i <= x - 1;i++){
        if(x % i == 0){
            ans = false;
            break;
        }
    }
    return ans;
}

方法一’：暴力枚举优化

思路分析

对于任何合数我们都可以表达成两个数相乘，因此，我们设一个数为$ x=ab $，则$ \sqrt{x} $=$ \sqrt{ab} $。令$ a>b $,那么a>$ \sqrt{ab} $>b，即a>$ \sqrt{x} $>b。因此，如果存在一个合数$ x $，那么必然存在一个因子小于$ \sqrt{x} $也就是说，我们只需要枚举到$ \sqrt{x} $的位置就可以了。

时间复杂度O($ \sqrt{n} $)

代码实现

bool isPrime(int x)
{
    bool ans = true;
    for(int i = 2;i <= (int)sqrt(x);i++){//(int)表示把后面的浮点数强行转化为整数。
        if(x % i == 0){
            ans = false;
            break;
        }
    }
    return ans;
}

方法二：素数表筛选法

思路分析

如果一个数是合数那么一定会存在一个非自身的因子为素数，因此我们只需要检查此数的因子有没有在素数表里。

代码实现

/*
  n:为要检测的数字
  count:素数表中素数的个数
  PrimeArray:素数表数组
*/
bool isPrime(int n; i <= count; int[] PrimeArray){
    for(int i = 0;i < count;i++){
        if(n % PrimeArray[i] == 0){
            return false;
        }
    }
    return true;
}