Problem 60 - Project Euler(途中)

30分プログラム、その340。Problem 60 - Project Euler。
素数判定の方法を変更してみた。きっとこれなら上手くいつはずだ。とりあえず、しばらく走らせてみよう。

使い方

$ 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.
#
import math

## 素数生成
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,1000))

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

def is_prime(p):
    for n in xrange(2,int(math.ceil(math.sqrt(p)))):
        if p % n == 0:
            return False
    return True
        

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__':
     i = 5
     while True:
         for choice in generate(i,5):
             print choice
             if is_satisfy(choice):
                 print choice
                 exit(0)
         i+=1

参考

• 過去の30分プログラム