文章目錄

原题链接http://projecteuler.net/problem=3

Largest prime factor
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的最大素数因子?

解法:
这一题本来想先求出600851475143的以内的素数,然后再从最小的素数开始,找到它的最大因子。可是程序运行时出现了OverflowError: Python int too large to convert to C long错误,也就是600851475143已经超出了C语言中整型的范围,这是因为xrange这个函数的范围限制在C的long长度,在32位的机器中,传入xrange的数不能大于2 ** 31 - 1.上网找这个错误时,在StackOverFlow中找到了这个错误的解答,其中有一个人给出了一个方法。
下面举例来说明这个方法,例如要求360的素数因子,先从素数2开始,360一直除以2知道不在整除,得到45;之后一直除以素数3知道不能整除,得到5;之后3 + 2得到5,于是除以5,得到1,结束。

文章目錄