素数とビット計算 with python

素数を求める関数を作ること自体は簡単だけど速く素数を見つけ出す計算はなるほどなと思わされた。そんなの思いつかんって。こちらが普通の素数を求める関数。特に変わったとこはなし。

prime

def is_prime(n):
    for c in range(2,n):
        if n%c ==0:
            return False
    return True

次に早く計算が出来るように改良されたアルゴリズム。さっきは引数のnの一つ手前までループしてたけど今回は 1+√n の一つ手前まで。つまり√n まで。ここだけトリッキーなところだけど理論自体はそんなに難しくない。まず、nが14だとすると、1,2,7,14でもって14を割り切ることができる。この時、2が14を割り切るとわかってしまえば7も14を割り切るってわかる。つまり対になっているものが存在するのだからほぼ半分くらい計算を省略できるんでない？っつーことか。ここで疑問に思うのがなんでn/2じゃなくて√nなんだろうということ。この対になっているのを求めるにはこの場合14/2=7をすればいい。これらによって2で割り切れるとわかると同時に7でも割り切れることがわかる。つまり、 n%a==0 が成り立つ時 n%(n/a)==0 もまた成り立つ。
ここで横軸a,縦軸y、そしてf=a,f=n/aの２つの関数（数学的な）を思い描いてみると、f=aは右肩上がりの直線、f=n/aは右肩下がりの曲線になっている。先ほどのアルゴリズムはこのf=aの直線のみを活用してnまでループしていたけど今回はこの２つの関数の交点にあたるところまでループを行えばいい。たぶん。つまり、n=14の時f=aの関数で2を調べることと、f=n/aで7を調べることが同義であるということか。

a=n/a
a*a=n
a=√n

よって√nまでのループでおk。視覚に訴えないとこれきついな…

fast_prime

def fast_is_prime(n):

    upper = int(n**0.5)

    prime=True

    for c in range(2,upper+1):

        if n%c ==0:

            prime = False

            break

    return prime

first-n_prime()関数は単純に引数nまでの素数をリストアップするだけ。

first_n_prime

def first_n_prime(n):
    ans=[ ]
    candidate=2
    while len(ans) < n:
        #find a new prime
        if fast_is_prime(candidate):
            ans.append(candidate)
        candidate+=1
    return ans

次はビットの計算。Cでは単純にビット演算子を使ったけど今回はまた別な方法。digitを求めるのに%を使っているのが憎いね。自分で実装してみてちょっと困ったのがStringで使えるメソッドとListで使えるメソッドがあんまり共通してなかったこと。StringでfindメソッドなところをListでは object in list みたいな書き方をしてるし。findでは探し物が見つからなかった時に-1を返すのにlistのindexメソッドの方ではエラーになるし。Scalaみたくコレクションをまたいで同じメソッドで処理ってのがあんまりできないんだな。

bit

 def int2bin(x):
    L=[ ]
    while x>0:
        digit=str(x%2)
        L.append(digit)
        x/=2
    L.reverse()
    return "".join(L)

another_bit

def int2binNew(x):
    ans=""
    while(x>0):
        digit=str(x%2)
        ans=digit+ans
        x/=2
    return ans