这是来自 Project Euler 网站的问题 3
我没有解决这个问题,但我可能猜你会知道我的方法是什么。现在我的问题是,如何处理超过 unsigned int 的数字?
有没有一种数学方法,如果有,我在哪里可以读到它?
您是否尝试过unsigned long long
甚至更好/更具体uint64_t
?
如果您想使用大于uint64_t
[2 64 -1] [64 位整数,无符号] 范围的数字,那么您应该查看 bignum:http ://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic 。
600,851,475,143 是问题给出的数字,2 64 -1 等于 18,446,744,073,709,551,615。它绝对足够大。
最近教了一个孩子,我知道素数分解,只要你有一个素数列表,这个算法就很简单。
def factor(n):
"""returns a list of the prime factors of n"""
factors = []
p = primes.generator()
while n > 1:
x = p.next()
while n % x == 0:
n = n / x
factors.append(x)
return factors
连续调用p.next()
产生一系列素数中的下一个值 {2, 3, 5, 7, 11, ...} 该伪代码与实际工作 Python 代码的任何相似之处纯属巧合。我可能不应该提到 的定义primes.generator()
短了一行(但一行有 50 个字符长)。我最初编写这个“代码”是因为 GNUfactor
程序不接受 log 2 ( n ) >= 40 的输入。
采用
long long
在海合会
和
__int64
在风险投资
采用
long long
这在 GCC 和较新版本的 Visual Studio(我相信 2008 及更高版本)中都受支持。
也许处理您的问题的最简单方法是使用 Python。Python 版本 > 2.5 支持内置长精度算术运算。精度仅取决于您的计算机内存。您可以从此链接找到有关它的更多信息。
在 Windows 中,如果您的编译器不支持 64 位整数,您可以使用LARGE_INTEGER和ULARGE_INTEGER。