• 压缩筛选法求1~N内的所有质数

用压缩筛选法求 1 ~ MAX_NUMBER 内的所有质数
  基于 John Moyer (jrm@rsok.com) 的 sieve2310 (http://www.rsok.com/~jrm/printprimes.html) 算法改写
原理: 考虑 30 = 2*3*5, 对任意非负整数N(即N>=0), 显然
  1. N*30 + 2*x (x = [0, 15]) 都能被2整除
  2. N*30 + 3*x (x = [0, 10]) 都能被3整除
  3. N*30 + 5*x (x = [0, 6]) 都能被5整除
因此, 除去2, 3, 5的倍数后, N*30+0 ~ N*30+29 这30个数中, 只有
  N*30+1, N*30+7, N*30+11, N*30+13, N*30+17, N*30+19, N*30+23, N*30+29
这8个数可能是质数. 也就是说, 30个整数只需要8个Bit就可以表示所有可能的质数
依此类推, 当 2310 = 2*3*5*7*11 时, 所有可能的质数为
  N*2310+1, N*2310+13, N*2310+17, ..., N*2310+13*13, N*2310+13*17, ..., N*2310+2309
共480个. 即只需要480 Bits就可以表示2310个整数中的所有可能的质数.

上传的附件 sieve.rar

  • 标 题：答复
  • 作 者：arab
  • 时 间：2009-05-21 23:03:40

三种算法占用的空间和时间对比(同一台机, 编译时无优化选项, 同样计算50000000的质数, 计算完后马上停止计时, 不包括输出结果的时间, 单位分别为字节和秒):
jrm版: sieve_size = 1298760, time = 2 (BIGINT = 32)
jrm版: sieve_size = 1298760, time = 5 (BIGINT = 64)
Loka版: sieve_size = 6250001, time = 1
梵听版: sieve_size = 50000000, time = 3
显然, jrm版因为有压缩表示, 占用的空间最小, 但索引转换产生了额外的计算量, 特别是BIGINT = 64时, 对性能的影响特别明显.
不过我不明白为什么Loka版一样有定位到某个Bit的额外计算, 但却比梵听版用时还少.

附其它两个版本的代码如下:
梵听版: http://bbs.pediy.com/showthread.php?t=89405
Loka版: http://bbs.pediy.com/showthread.php?t=89406

  • 标 题：答复
  • 作 者：Loka
  • 时 间：2009-05-22 01:37:26

按你的方法写了个程序，不过我没用到11，只用到5。

代码:
#include <stdio.h>
#include <math.h>

#define NUM 50000000
typedef unsigned char BYTE;
BYTE table[NUM/30+1];

void suShu()
{
  int i, j, k, u, x, y, z;
  int predict[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  int xbit[8] = {1, 7, 11, 13, 17, 19, 23, 29};
  int flag[30];
  int halfNum;

  for(i=0; i<30; i++) flag[i] = 8;
  for(i=0; i<8; i++) flag[xbit[i]] = i;
  table[0] = 1;
  halfNum = (int)sqrt(1.0*NUM)-29;

  for( j=0,k=0; k<halfNum; j++,k+=30 )
  {
    for(i=0; i<8; i++)
    {
      if (((table[j]>>i)&1) == 0)
      {
        z = k+xbit[i];
        u = z%30;
        y = z*z;
        x = y%30;
        for( ; y<=NUM; y+=z)
        {
          if (flag[x] < 8) table[y/30] |= (1<<flag[x]);
          x += u;
          if (x >= 30) x -= 30;
        }
      }
    }
  }
  halfNum += 30;
  for(i=0; i<8; i++)
  {
    if (((table[j]>>i)&1) == 0)
    {
      z = k+xbit[i];
      if (z < halfNum)
      {
        u = z%30;
        y = z*z;
        x = y%30;
        for( ; y<=NUM; y+=z)
        {
          if (flag[x] < 8) table[y/30] |= (1<<flag[x]);
          x += u;
          if (x > 30) x -= 30;
        }
      }
    }
  }

  for( k=0; k<10; k++) printf("%10d", predict[k]);

  for( j=1,k=30; k<=NUM-30; j++,k+=30 )
  {
    for(i=0; i<8; i++)
    {
      if (((table[j]>>i)&1) == 0)
      {
        printf("%10d", k+xbit[i]);
      }
    }
  }
  for(i=0; i<8; i++)
  {
    if (((table[j]>>i)&1) == 0)
    {
      if ((k+xbit[i]) <= NUM) printf("%10d", k+xbit[i]);
    }
  }
  printf("\n");
}

int main()
{
  suShu();

  return 0;
} 

  • 标 题：答复
  • 作 者：EvilKnight
  • 时 间：2009-07-01 10:31:45

代码:
#define MAX 1229
int a[MAX]={2,3,5};
char s[10240] = {0,0,1,1,0,1};

void prime()
{
    int i,j,k,d,stat;
    k = 3;
    d = 2;
    for (i = 7;k < MAX; i += d)
    {
        stat = 1;
        d = 6-d;
        for (j = 0; a[j]*a[j] <= i  && stat; ++j)
        {
            if (i%a[j] == 0)
                stat = 0;
        }
        if (stat)
        {
            a[k] = i;
            s[i] = 1;
            ++k;
        }
    }
}

int main()
{
    prime() ;
    return 0 ;
}
你们测试下这个的效率,如果要大一点,自己修改.MAX是质数的个数,

以前做http://acm.hdu.edu.cn/showproblem.php?pid=2098
这题写的代码了!