最大的素数为：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