首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

[Project Euler]Problem 3

作者:  时间: 2011-04-14

Problem 3:
  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?

  13195的素因子为 5,7,13和29.
  求600851475143的最大素因子.

本题考的是分解因式.
     用factor取 2 以及比2大的奇数(素数集合的父集) 除n,直到 factor2>n,如果n不等于1,因为n不能被小于n的平方根整除,则n为素数.

def factors(n):
factor
=2
while factor**2<=n:
while n%factor==0:
n
=n//factor
yield factor
factor
+=(2 if factor!=2 else 1)
if n!=1:
yield n
def f(n):
return max(factors(n))