素数算法

Fibonacci和公约数公倍数算法见 斐波那契数列和公约数算法

/* 扫描[left, right]内的所有素数，返回个数
   方法：考虑跳过2和3的倍数，6n+1~6n+5中只需测试6n+1和6n+5
   [reference] http://blog.csdn.net/redraiment/archive/2008/01/29/2071998.aspx
*/
int filter_prime(int result[], int left, int right)
{
 int j, count = 0;

 if (left > right || right <= 1)
  return 0;

 if (left<=2 && right>=2)
  result[count++] = 2;

 if (left<=3 && right>=3)
  result[count++] = 3;

 int test = 5, inc = 2;
 while (test < left)
 {
  test += inc;
  inc = 6-inc;
 }

 while (test <= right)
 {
  int flg = 1;
  for (j = 2; j*j <= test; ++j)
  {
   if (0 == test%j)
   {
    flg = 0;
    break;
   }
  }

  if (1 == flg)
   result[count++] = test;

  test += inc;
  inc = 6 - inc;
 }

 return count;
}

/* 简单判断是否为素数，适合num为小数的情况
   是返回1， 否返回0
*/
int is_prime(int num)
{
 if (num <= 1)
  return 0;

 if (num==2 || num==3)
  return 1;

    int i;
    for (i = 2; i*i <= num; i++)
    {
        if ( 0 == num%i)
            return 0;
    }

    return 1;
}