Problem47

30分プログラム、その321。Problem47 - Project Euler。

連続する2つの数がそれぞれ2つの異なる素因数を持つのは

• 14 = 2 × 7
• 15 = 3 × 5

の場合である.

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

• 644 = 22 × 7 × 23
• 645 = 3 × 5 × 43
• 646 = 2 × 17 × 19 の場合である.

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

とりあえず、総当たりで計算するプログラムを書いてみた。あと30分ほど走らせて、無理だったら別の方法を考えよう。
あと、必要な素数の上限が分らないからどうしようか迷ったけれども、とりあえず動的計画法でごまかしておいた。

使い方

$ pytohn problem47.py
...

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem47.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/06/14 23:06:44
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
import math

hash = {2:True}

def is_prime(n):
    if n in hash:
        return hash[n]
    else:
        upper = int(math.ceil(math.sqrt(n)))
        for x in xrange(2,upper+1):
            if n % x == 0:
                hash[n] = False
                return False
        hash[n] = True
        return True
        
def factor(n):
    m = 0
    for p in xrange(2,n):
        if is_prime(p) and n % p == 0:
            m += 1
    return m

def main():
    # 12515
    i = 0
    while True:
        print i,factor(i)
        if (factor(i)   == 4 and 
            factor(i+1) == 4 and
            factor(i+2) == 4 and
            factor(i+3) == 4):
            return i
        i += 1

if __name__ == '__main__':
    print main()

参考

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