素数シーケンス

30分プログラム、その290。Pythonで素数シーケンス。

• 昨日の問題(id:mzp:20080420:abundant)を解くには、高速に約数を計算する必要がある
• そのためには素因数分解が必要だ
• そのためには素数が必要だ
• だから、Pythonで素数を計算しよう

ジェネレータを使ったほうがメモリに優しい気がしたので、ガンガン使ってみた。

使い方

>>> xprint(xtake(5,primes()))
2
3
5
7
11

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem23.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/04/19 09:26:46
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
def xfilter(f,range):
    for x in range:
        if f(x):
            yield x

def xprint(range):
    for x in range:
        print x

def xtake(n,xs):
    for x in xs:
        if n > 0:
            n -= 1
            yield x
        else:
            break

def xtakeWhile(f,xs):
    for x in xs:
        if f(n):
            n -= 1
            yield x
        else:
            break

def primes():
    (n,xs) = (2,[])
    while True:
        if all(map(lambda x: n % x != 0,xs)):
            xs.append(n)
            yield n
        n += 1

参考

• 過去の30分プログラム