Problem60 - Project Euler(途中)

30分プログラム、その339。Problem 60 - Porject Euler。id:mzp:20080713:eulerの続き。
エラトステネスの古いが、再起が深すぎてRuntimeエラーがでてしまうのでwhileで書き直したりしてみたけれど、そもそもこれだと遅すぎで全然解けない。別の方法を考えないとダメだろう。

使い方

$ python problem60.py
....

ソースコード

#! /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):
    ps = []
    xs.reverse()
    while xs != []:
        n = xs.pop()
        ps.append(n)
        l = len(xs)
        for i in range(0,l):
            if xs[l-i-1] % n == 0:
                del xs[l-i-1]
    return ps
primes = sieve(range(2,200000))

## 条件を満すかの判定
def digit_concat(x,y):
    return int(str(x)+str(y))

def is_prime(p):
    for x in primes:
        if p == x:
            return True
        elif p < x:
            return False
    raise "over:"+str(p)

def is_satisfy(xs):
    for x in xs:
        for y in [y for y in xs if y != x]:
            if not (is_prime(digit_concat(x,y)) and 
                    is_prime(digit_concat(y,x))):
                return False
    return True
            
            

## 組の生成
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


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

if __name__ == '__main__':
    print is_satisfy([3,7,109,673])
#     i = 3
#     while True:
#         for choice in generate(i,4):
#             print choice
#             if is_satisfy(choice):
#                 print choice
#                 exit(0)
#         i+=1

参考

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