c++ - 处理大量

Question

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

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

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

score 5 · Accepted Answer

您是否尝试过unsigned long long甚至更好/更具体uint64_t？

如果您想使用大于uint64_t[2 ⁶⁴ -1] [64 位整数，无符号] 范围的数字，那么您应该查看 bignum：http ://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic 。

600,851,475,143 是问题给出的数字，2 ⁶⁴ -1 等于 18,446,744,073,709,551,615。它绝对足够大。

score 4 · Accepted Answer

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

从 2 开始，尽可能多地将其划分为目标，并留下零余数。
取下一个素数 (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 ₂ ( n ) >= 40 的输入。

score 0 · Accepted Answer

0

采用

long long

在海合会

和

__int64

在风险投资

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

score 0 · Accepted Answer

采用

long long

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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

在 Windows 中，如果您的编译器不支持 64 位整数，您可以使用LARGE_INTEGER和ULARGE_INTEGER。

c++ - 处理大量

7 回答 7

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

Related

Reference