素数のリストを生成する（エラトステネスの篩）

Project Euler の第3問は素因数を求める問題なので、まずは素数のリストを生成しようということで「エラトステネスの篩（エラトステネスのふるい）」というアルゴリズムを使用して任意の n 以下の素数のリストを生成するコードを書いてみました。

エラトステネスの篩 - Wikipedia

class Eratos(object):
    """ n 以下の素数リストを生成する"""
    def __init__(self, n):
        self.prime = []
        self.mainlist = [i for i in xrange(2, n+1)]

    def search_prime(self):
        top_number = self.prime.append(self.mainlist[0])
        [[(i % n == 0) and self.mainlist.remove(i) for i in self.mainlist ] for n in self.prime]
        if self.prime[-1] ** 2 < self.mainlist[-1]:
            self.search_prime()
        else:
            self.prime = self.prime + self.mainlist
            return self.prime

>>> ins = Eratos(30)
>>> ins.search_prime()
>>> ins.prime
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

n が大きいとエラーになる

Project Euler 第3問で調べる数値は「600851475143」ですが、このコードだと数値が大きすぎてエラーになってしまいました。

>>> ins = Eratos(600851475143)
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
  File "D:\python\pe3.py", line 10, in __init__
    self.mainlist = [i for i in xrange(2, n+1)]
OverflowError: long int too large to convert to int

600851475143という数値はlong型になっちゃうみたいですね。int(600851475143)とかやってみましたが無駄でした。ちなみにxrangeをrangeに変えた場合「OverflowError: range() result has too many items」となるのでこれもダメ。そもそもがもうちょっと小さな数値で試したところ「MemoryError」と出たので、数値が大きすぎるのが問題みたいです。

改良すればなんとかなるのかすら微妙ですが、もうちょっと煮詰めてみようと思います。