i 番目の素数を、整数のバイナリ表現で i 番目のビットを 1 として表現してみる。例えば 2 の倍数を篩にかけるときは、10101010…1000というバイナリ表現の整数とビットオア演算するという感じ。

#! /usr/local/bin/python



import psyco

psyco.full()



def zebraBit(span, length):

  bitkun = 2L ** (span - 1)

  for initan in range(1, length/span):

    bitkun = (2L ** (span - 1) << (initan * span)) | bitkun

  return bitkun



def binArray2intList(intasbin):

  integers = []

  count = 0

  num = intasbin

  while num > 0:

    if intasbin & (1L << count):

      pass

    else:

      integers.append(count + 1)

    num = num >> 1

    count = count + 1

  return integers[1:]



bit = 0L

for i in range(2, 100):

  bit = zebraBit(i, 10000) - (1L << (i-1)) | bit



m = binArray2intList(bit)

print len(m)

print m[len(m)-1]

これがちっとも早くない。しかも、ほとんどがビット演算なだけに、psycoを使ってもたいして変わらない。

$ time python prime2.py

1229

9973

3.980u 0.020s 0:03.99 100.2%    0+0k 0+0io 374pf+0w

整数を順番に素数のリストで篩にかけるのより遅い。もちろん、psycoなしで比較すると、圧倒的に今日の素数ジェネレータのほうが早い。

$ time python prime.py 1229

1229 th prime is 9973

2.690u 0.010s 0:02.71 99.6%     0+0k 0+0io 344pf+0w