素数のリストを生成する(エラトステネスの篩)
Project Euler の第3問は素因数を求める問題なので、まずは素数のリストを生成しようということで「エラトステネスの篩(エラトステネスのふるい)」というアルゴリズムを使用して任意の n 以下の素数のリストを生成するコードを書いてみました。
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」と出たので、数値が大きすぎるのが問題みたいです。
改良すればなんとかなるのかすら微妙ですが、もうちょっと煮詰めてみようと思います。