最大的素数为：999983

一、素数介绍

  素数又称为质数，是除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n ，如果对任意的正整数 a(1 < a < n)，都有 n % a != 0 成立，那么称 n 是素数，否则，如果存在正整数 a(1 < a < n)，都有 n % a == 0 成立，那么称 n 为合数。（1既不是素数，也不是合数）

二、素数的判断

  只需要判断 n 是否能被 2,3，···，sqrt(n)(向下取整)，即可判断 n 是否为素数。该算法的时间复杂度为 O(sqrt(n));

C代码如下：

bool isPrime(int n){
    int i;
    if(n <= 1){
        return false;
    }
    int sqr = (int)sqrt(1.0 * n);   //sqrt()的参数要求是浮点数
    for(i = 2; i < sqr; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

更简单的写法：

bool isPrime1(int n){ 
    int i;
    if(n <= 1){
        return false;
    }
    for(i = 2; i * i <= n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

三、获取素数表

const int maxn 101;      //表长
int prime[maxn],pNum = 0;
bool p[101] = {0};  //p[i] == true表示 i 是素数
void find_Prime(){
    int i;
    for(i = 1; i < maxn; i++){
        if(isPrime(i) == true){
            prime[pNum++] = i;
            p[i] = true;
        }
    }
}

更高效的算法------埃氏筛法：Eratosthenes

  埃氏筛法的具体思想是：在对每一个数判断是否是素数时，将其所有倍数都标记为非素数，这样，在后面遇到这个数的倍数时，就不用一一从头开始判断是否能被其他数整除了。

const int maxn 101;      //表长
int prime[maxn],pNum = 0;
bool p[101] = {0};  //p[i] 为false表示 i 是素数，true 表示 i 不是素数

void find_Prime1(){
    int i,j;
    for(i = 2; i < maxn; i++){
        if(p[i] == false){        
            prime[pNum++] = i;
            for(j = i + i; j < maxn; j += i){
                p[j] = true;
            }
        }
    }
}

使用

LeetCode 204