Problem 60 - Project Euler(途中)

30分プログラム、その338。Problem 60 - Project Euler。

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の組の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

これは結構大変だぞ。いい方法が思いつかなかったので、直接求めてみることにした。で、今日は5つの素数の組を生成するところまで。

使い方

$ python problem60.py
[11, 7, 5, 3, 2]
[13, 7, 5, 3, 2]
[13, 11, 5, 3, 2]
[13, 11, 7, 3, 2]
[13, 11, 7, 5, 2]
[13, 11, 7, 5, 3]
[17, 7, 5, 3, 2]
[17, 11, 5, 3, 2]
[17, 11, 7, 3, 2]
[17, 11, 7, 5, 2]
...

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem60.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/07/13 22:09:50
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

def sieve(xs):
    if xs == []:
        return xs
    else:
        n = xs[0]
        return [n]+sieve(filter(lambda x: x % n  != 0,xs[1:]))

def make(count,up):
    if count == 1:
        for x in xrange(up):
            yield [x]
    else:
        for next_up in xrange(count-2,up):
            for y in make(count-1,next_up):
                yield [next_up] + y

primes = sieve(range(2,1000))
def generate(max,n):
    for x in make(n-1,max):
        yield map(lambda n:primes[n],[max]+x)

i = 4
while True:
    for choice in generate(i,5):
        print choice
    i+=1

参考

• 過去の30分プログラム
• Problem 60 - PukiWiki