6

这是来自 Project Euler 网站的问题 3

我没有解决这个问题,但我可能猜你会知道我的方法是什么。现在我的问题是,如何处理超过 unsigned int 的数字?

有没有一种数学方法,如果有,我在哪里可以读到它?

4

7 回答 7

5

您是否尝试过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。它绝对足够大。

于 2010-05-23T06:10:26.397 回答
4

最近教了一个孩子,我知道素数分解,只要你有一个素数列表,这个算法就很简单。

  1. 从 2 开始,尽可能多地将其划分为目标,并留下零余数。
  2. 取下一个素数 (3) 并将其划分为目标,如第一步
  3. 写下你发现的每个因素并重复,直到用完剩余部分。

根据请求添加了算法伪代码:

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 的输入。

于 2010-05-23T06:28:13.397 回答
0

采用

long long

在海合会

__int64

在风险投资

于 2010-05-23T06:09:52.043 回答
0

采用

long long

这在 GCC 和较新版本的 Visual Studio(我相信 2008 及更高版本)中都受支持。

于 2010-05-23T06:12:55.440 回答
0

也许处理您的问题的最简单方法是使用 Python。Python 版本 > 2.5 支持内置长精度算术运算。精度仅取决于您的计算机内存。您可以从此链接找到有关它的更多信息。

于 2010-05-23T06:19:34.943 回答
0

long long会为这个问题做的。对于其他超出的 Project Euler 问题long long,我可能会使用libgmp(特别是它的C++ 包装类)。

于 2010-05-23T06:22:52.050 回答
0

在 Windows 中,如果您的编译器不支持 64 位整数,您可以使用LARGE_INTEGERULARGE_INTEGER

于 2010-05-23T07:16:14.750 回答