写在前面

网上关于判断一个数是否是素数的方法有很多种，而且分析也比较成熟。
这里简单介绍一种比较普通的方法：
对于一个自然数，如果存在可整除的数，即X = a * b, 那么因数中必定会有一个因数小于 而另一个因数大于。所以X如果不能整除[2,]的范围内的整数，则证明该数为素数。

a问 代码实现

输入条件：N为正整数。

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n){
    if(n==1){//1不是素数
        return false;
    }
    if(n==2){//2 单独判断
        return true;
    }
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
            break;
        }
    }
    return true;
} 
int main(){
    cout<<isPrime(3)<<endl;
}

B 问

最坏情况下运行时间是： O（）

C 问

将 N 转化为二进制（所能表示N的最小位数的二进制，不算符号位），并将二进制位都置为1，则有如下对应关系：

,所以B=O(logN),这里的大O标记我认为表示的是，B和logN的增长速度相同。

D 问

根据C问所述，，时间复杂度是：O(logN)，故而：

e 问和F问

根据D问可得：

后面：

当然判断一个数是否是素数的方法很多，资料如下：
素数算法吐血总结 //这个注重了思考过程
素数算法 //这个比较全