最大素因数分解の探索

Python 30分プログラム

30分プログラム、その261。最大素因数分解の探索(Project Euler)。

13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

√600851475143からはじめて、最大の素因数を探してみた。

Pythonのxrangeはintの範囲を越えると使えないし、rangeでは生成される要素数が多すぎると言われてしまう。しょうがないので、whileでループを書いた。

使い方

$ python prime.py
6857

だいたい1分ほどかかる。

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# prime.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/03/13 21:27:01
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
from math import ceil,sqrt

def isDiv(x,y):
  return x % y == 0

def isPrime(x):
  for n in xrange(2,long(ceil(sqrt(x)))):
    if isDiv(x,n):
      return False
  return True

def findMaxFactor(x):
  n = long(ceil(sqrt(x)))
  while n > 0:
    print n
    if isDiv(x,n) and isPrime(n):
      return n
    n -= 1 
  return None

print findMaxFactor(600851475143)

参考