充分に大きな素数が欲しいといっても、そこまで凝る必要はないような気がするので、せいぜい32bit くらいでいいでしょう。

すくなくとも無いよりましだし、hiddenタグがあまりに肥大化するのもやです。

こんな感じで素数を生成するのはどうでしょう

def primes(max=100, start=None): # max が最大数、startが素数を求めはじめる数
    sqrmax = int(max**0.5) + 1 # 割り算は最大数の平方根までで充分 +1は念の為
    if max > 65536: # 最大32bitと考えてハードコード
        if sqrmax % 2 == 0: sqrmax += 1 # 奇数にする
        if start:
            if start %2 == 0: start -= 1 # 奇数にする
        else: #スタートがなければ、平方根値をスタートとする。-2は念の為
            start = sqrmax - 2
        r = primes(sqrmax)
        c = [x for x in xrange(start, max+1, 2) if x%3 and x%5] # 2, 3, 5はあらかじめはぶく
        for x in r[3:]: # 7からエラストネス
            c = [y for y in c if y%x]
    else: # 小さい場合は普通にハードコード
        r, c = [2, 3],  [x for x in xrange(5, max, 2) if x%3] # 2, 3を省く
        while c[0] <= sqrmax: 
            r.append(c[0]) # 先頭のものは素数
            c = [x for x in c if x % c[0]] # なぜかというとここで先頭のものの倍数を全て除去するので
    return r + c

これで、32bit長くらいの素数なら作れると思います。動作もmaxに近いところを500整数くらいやるようにすれば0.1秒はかからないでしょう