一个数，如果只有1和它本身两个因数，这样的数叫做质数，又称素数。

在上文 《素数算法大全，及C程序实现优化详解 (一) 试除法》中我们已经探讨了求解素数的一类算法，并且将试除法从最初的低效版本优化的高效的V2。那么，还有没有其它更佳算法呢？这就是下面三藏要和大家探讨的内容

合数过滤筛选法

算法描述：我们知道，素数N不能被2~(N-1)间的任何数整除；反过来看，只要能被2~(N-1)间的任何数整除的N，都不是素数。所以我们可以采用一个简单的排除法：就是对N以内的所有数，只要逐个去除值为2~(N-1)的倍数的数，剩下的就是素数。

C语言实现

// 合数过滤筛选法 Ver1 
// 参数：n 求解n以内(包括n)的素数
// 返回值：n以内素数个数 
int CompositeNumFilterV1(int n)
{
 int i, j;
 // 素数数量统计 
 int count = 0;
 // 分配素数标记空间，结合后文思考为何+1
 char* flag = (char*)malloc( n+1 ); 
 
 // 初始化素数标记 
 for (i=2; i<=n; i++)
 {
  // 为什么*(p+i)要写成flag[i]呢？可读性更佳尔 
  flag[i] = 1;
 }
 
 // 写程序要注意排版和留空，方便阅读，也可减少出错几率
 // 以2~(N-1)为因子过滤合数 
 for (i=2; i < n; i++)
 {
  for (j=2; i*j <= n; j++)
  {
   // i*j是由i,j两整数相乘而得，显然不是素数
   flag[i*j] = 0;
  }
 }
 
 // 统计素数个数
 for (i=2; i<=n; i++)
 {
  // 其实if(flag)就其同样作用了，但这么写是有留言的 
  // 请参阅《C语言程序设计常见错误剖析及解决之道》一文 
  if (1 == flag[i]) count++;
 }
  
 // 因输出费时，且和算法核心相关不大，故略
  
 // 释放内存，别忘了传说中的内存泄漏 
 free(flag);
 
 return count;
} 

在上文给出的main函数中以不同参数调用CompositeNumFilterV1函数，得到执行结果如下：

[100000]以内素数个数：9592, 计算用时：15毫秒
[1000000]以内素数个数：78498, 计算用时：125毫秒
[5000000]以内素数个数：348513, 计算用时：2578毫秒
[10000000]以内素数个数：664579, 计算用时：6281毫秒

注：因程序是非独占性运行的，所以时间不是完全精确的，但基本能反映实情

显然，比上文中的试除法要快，而且谁都可以看到上例是一个未经优化的粗陋版本，好多地方是三藏故意采用比较低效做法，为了与后文的优化版比较，凸显优化之重要，也为了初学者记住别采用类似低效做法，下面我们开始优化之旅

优化分析

上面CompositeNumFilterV1函数存在的问题有：

1. 在外层循环，需要一直执行到n-1吗？不要，因为n/2~n-1间的数显然不能整出n
2. 在内层循环中重复使用i*j显然是低效的，考虑到计算机中加减运算速度比乘除快，可以考虑变乘法为加法
3. 在循环修改flag过程中，其实有很多数会被重复计算若干次，比如6=2*3=3*2，会被重复置0，类似操作很多，所以我们得设法避免或减少flag重复置0

据上述分析，我们可将程序优化如下：

// 合数过滤筛选法 Ver2 
// 参数：n 求解n以内(包括n)的素数
// 返回值：n以内素数个数 
int CompositeNumFilterV2(int n)
{
 int i, j;
 // 素数数量统计 
 int count = 0;
 // 分配素数标记空间，明白+1原因了吧，因为浪费了一个flag[0]
 char* flag = (char*)malloc( n+1 ); 
 
 // 初始化素数标记，要高效点咯
 flag[2] = 1;
 // 注意是i<n不是上例中的i<=n了，理由自思 
 for (i=3; i<n; i++)
 {
  flag[i++] = 1;
  // 偶数自然不是素数，直接置0好了 
  flag[i] = 0;
 }
 // n为奇数 
 if (n%2 != 0)
 {
  flag[n] = 1;
 }
 
 // 从3开始filter，因为2的倍数早在初始化时代就干掉了
 // 到n/2止的理由还要说吗 
 for (i=3; i <= n/2; i++)
 {
  // i是合数，请歇着吧，因为您的工作早有您的质因子代劳了 
  if (0 == flag[i]) continue;
  
  // 从i的2倍开始过滤，变乘法为加法  
  for (j=i+i; j <= n; j+=i)
  {
   flag[j] = 0;
  }
 }
 
 // 统计素数个数
 for (i=2; i<=n; i++)
 {
  if (flag[i]) count++;
 }
  
 // 因输出费时，且和算法核心相关不大，故略
  
 // 释放内存，别忘了传说中的内存泄漏 
 free(flag);
 
 return count;
} 

再来调用CompositeNumFilterV2得到执行结果：

[100000]以内素数个数：9592, 计算用时：n太小，时间精度不够
[1000000]以内素数个数：78498, 计算用时：31毫秒
[5000000]以内素数个数：348513, 计算用时：453毫秒
[10000000]以内素数个数：664579, 计算用时：1062毫秒
[100000000]以内素数个数：5761455, 计算用时：12973毫秒

哇哇，比昨天的试除发快了好多倍，可见算法的威力，值得好好学习，别说学算法没用咯。

上例着那个计算一亿以内的素数只要约13秒，应该算不错了，今天是否可以休息了呢？No，我们要追求极限！

int CompositeNumFilterV3(int n)
{
 int i, j;
 // 素数数量统计 
 int count = 0;
 // 分配素数标记空间，明白+1原因了吧，因为浪费了一个flag[0]
 char* flag = (char*)malloc( n+1 );
 // 干嘛用的，请仔细研究下文
 int mpLen = 2*3*5*7*11*13;
 char magicPattern[mpLen];
 // 奇怪的代码，why，思考无法代劳，想！ 
 for (i=0; i<mpLen; i++)
 {
  magicPattern[i++] = 1;
  magicPattern[i++] = 0;
  magicPattern[i++] = 0;
  magicPattern[i++] = 0;
  magicPattern[i++] = 1;
  magicPattern[i] = 0;
 }
 for (i=4; i<=mpLen; i+=5)
  magicPattern[i] = 0;
 for (i=6; i<=mpLen; i+=7)
  magicPattern[i] = 0;
 for (i=10; i<=mpLen; i+=11)
  magicPattern[i] = 0;
 for (i=12; i<=mpLen; i+=13)
  magicPattern[i] = 0;
 
 // 新的初始化方法,将2,3,5,7,11,13的倍数全干掉
 // 而且采用memcpy以mpLen长的magicPattern来批量处理 
 int remainder = n%mpLen;
 char* p = flag+1;
 char* pstop = p+n-remainder;
 while (p < pstop)
 {
  memcpy(p, magicPattern, mpLen);
  p += mpLen;
 }
 if (remainder > 0)
 {
  memcpy(p, magicPattern, remainder);
 }
 flag[2] = 1;
 flag[3] = 1;
 flag[5] = 1;
 flag[7] = 1;
 flag[11] = 1;
 flag[13] = 1;
 
 // 从17开始filter，因为2,3,5,7,11,13的倍数早被kill了 
 // 到n/13止的，哈哈，少了好多吧
 int stop = n/13;
 for (i=17; i <= stop; i++)
 {
  // i是合数，请歇着吧，因为您的工作早有您的质因子代劳了 
  if (0 == flag[i]) continue;
  
  // 从i的17倍开始过滤
  int step = i*2;
  for (j=i*17; j <= n; j+=step)
  {
   flag[j] = 0;
  }
 }
 
 // 统计素数个数
 for (i=2; i<=n; i++)
 {
  if (flag[i]) count++;
 }
  
 // 因输出费时，且和算法核心相关不大，故略
  
 // 释放内存，别忘了传说中的内存泄漏 
 free(flag);
 
 return count;
}

再看CompositeNumFilterV3执行结果：

[1000000]以内素数个数：78498, 计算用时：15毫秒
[5000000]以内素数个数：348513, 计算用时：203毫秒
[10000000]以内素数个数：664579, 计算用时：515毫秒
[100000000]以内素数个数：5761455, 计算用时：6421毫秒

再次优化后速度提升了又一倍左右，三藏不禁有点满足了，睡觉也！

质数的定义

一个数，如果只有1和它本身两个因数，这样的数叫做质数，又称素数。 

试除判断法

算法描述：从上述定义可知，素数不能被1和它本身之外的数整除，所以，判断一个数x是否素数只要看它是否能被2~sqrt(x)间的数整除即可；而求N内所有素数则是循环重复上述过程。

C语言实现：

#include <time.h>
#include <malloc.h> 
#define N 100000
// 简单试除判断法 Ver1 
int SimpleDivisionV1(int n)
{
 int i,j;
 // 素数数量统计 
 int count = 0;
 // 分配存放结果的空间 
 int* primes = (int*)malloc( sizeof(int)*n ); 
 
 // 2是素数谁都知道，不算了 
 primes[count++] = 2;
 // 循环计算3~n间的数 
 for (i=3; i<=n; i++)
 {
  // 为什么是sqrt(i)，思考一下 
  for (j=2; j<=sqrt(i); j++)
  {
   // i被j整除，显然不是素数了 
   if (i%j == 0) break;
  }
  // i不能被2~sqrt(i)间的数整除,素数也 
  if (j > sqrt(i))
  {
   primes[count++] = i;
  }
 }
 
 // 因输出费时，且和算法核心相关不大，故略
  
 // 释放内存，别忘了传说中的内存泄漏 
 free(primes);
 
 return count;
} 

void main()
{
 int count;
 clock_t start, end;
 // time函数不够精确，用clock凑合一下吧 
 start = clock(); 
 count = SimpleDivisionV1(N);
 
 end = clock();
 printf("[%d]以内素数个数：%d, 计算用时：%d毫秒\n", N, count, end-start);
 getch(); 
}

计算结果：
[100000]以内素数个数：9592, 计算用时：468毫秒
[1000000]以内素数个数：78498, 计算用时：10859毫秒
[5000000]以内素数个数：348513, 计算用时：103560毫秒

噢噢，算算十万还行，百万就10秒多了，而且时间增长很快，这不行，得优化一下！

优化分析：

仔细研究一下SimpleDivisionV1我们可以发现以下几个问题：

1. 在循环条件中重复调用sqrt(i)显然是比较浪费时间的
2. 判断素数，真的需要拿2~sqrt(i)间的所有整数去除吗？我们知道，合数都可以分解成若干质数，所以只要2~sqrt(i)间的质数不能整除i即可

根据上面两点，我们可将SimpleDivisionV1升级为SimpleDivisionV2，如下

 // 简单试除判断法 Ver2 
int SimpleDivisionV2(int n)
{
 int i, j, k, stop;
 // 素数数量统计 
 int count = 0;
 // 分配存放结果的空间 
 int* primes = (int*)malloc( sizeof(int)*n ); 
 
 // 2是素数谁都知道，不算了 
 primes[count++] = 2;
 stop = count;
 // 循环计算3~n间的数 
 for (i=3; i<=n; i++)
 {
  k = sqrt(i);
  // 在循环条件中重复调用sqrt是低效做法，故引入k 
  while (primes[stop] <= k && stop < count)
   stop++;
  // stop干什么用，思考一下
  for (j=0; j<stop; j++)
  {
   if (i%primes[j] == 0) break;
  }
  // i不能被2~sqrt(i)间的素数整除，自然也不能被其他数整除,素数也 
  if (j == stop)
  {
   primes[count++] = i;
  }
 }
 
 // 因输出费时，且和算法核心相关不大，故略
  
 // 释放内存，别忘了传说中的内存泄漏 
 free(primes);
 
 return count;
} 

然后将main中调用的函数替换为SimpleDivisionV2，在看一下执行结果：

[100000]以内素数个数：9592, 计算用时：46毫秒
[1000000]以内素数个数：78498, 计算用时：546毫秒
[5000000]以内素数个数：348513, 计算用时：3515毫秒
[10000000]以内素数个数：664579, 计算用时：8000毫秒

很开心的看到，经过优化，速度提高了几十倍，尤其是时间增长曲线的坡度变小了，N值越大，V2函数比V1的效率就越高

对于试除判断这种质数算法来说，三藏认为SimpleDivisionV2基本已经接近极限，不大可能有量级上的突破了，有兴趣的朋友可以自己进一步优化。初学者除了参看上述例子外，可以尝试做各种修改及细节优化，也可以将除法变乘法，多加练习是学习编程的好方法。

虽然，上例中V2已经比V1快了很多了，但随着N的增大，耗时还是不少，那么我们还有更好的方法吗？

里面包括：

线性表——静态链表2009.7.30
线性表——链表的内部类实现2008.8
线性表——链表的友元类实现2008.8
线性表——双向链表2009.8.11
线性表——顺序表2009.8.3
线性表——友元模板类2009.8

约瑟夫问题——四种解法2009.8.11（数组，链表，循环链表等）
队列——队列的顺序表示循环队列2009.8.11
队列——链队列2009.8.11
栈——汉诺塔2009.8.6
栈——进制转换2009.8.6
栈——括号匹配2009.8.6
栈——模板链栈2009.8.3
栈——模板顺序栈2009.7
栈——顺序栈2009.8.6
栈——算术表达式求值2009.7.13
栈——行编辑2009.8.6
二叉树——二叉树的常见操作2009.9.3

2010.3.9 更新

树的应用—仿DOS文件夹管理程序

200位大数乘法.rar

200位大数加法.rar

连连看单机程序MFC