2005/01/02

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

No comments :