问题标签 [factorization]

可能的重复：
第 n 个丑数
找到表达式 (2^x)*(3^y)*(5^z) 的第 K 个最小数

我想知道如何以快速而优雅的方式解决这个问题：

我们定义每个可以写成以下形式的数字n的“丑陋” ：2^x * 3^y * 5^z;，其中 x,y 和 z 是自然数。找到第 1500 个丑数。

例如，第一个“丑陋”的数字是：

我试图通过这种方式使用蛮力解决这个问题：

但这需要相当多的时间，我想找到一个更快更好的解决方案。

我知道丑数的主要因素，但我想不出按照正确顺序生成这些数字的方法。

我认为必须有一种方法可以生成这些数字，而无需检查所有数字。问题是，主要因子的指数似乎是随机分布的。

看这张表：

如您所见，x、y 和 z 值似乎不遵循任何规则。

你们中有人能找到解决这个问题的方法吗？

我正在考虑尝试将问题划分为不同的部分。由于问题是由指数的随机性决定的，我可以尝试独立生成 2s、3s、5s 的幂，然后生成 2^x*3^y、2^x*5^z 等形式的数字。最后把它们放在一起，但我不知道这是否能解决我的问题。

我最近偶然发现了一篇关于Pollard 的 Rho 算法并行化的论文，鉴于我的具体应用，除了我没有达到所需的数学水平之外，我想知道这种特殊的并行化方法是否有助于我的具体情况.

我试图找出两个因数——半素数——非常大。根据我对这篇论文的了解，我的假设是，这种并行化在具有许多较小因子的数字上运行良好，而不是在两个非常大的因子上。

这是真的？我应该使用这种并行化还是使用其他东西？我什至应该使用 Pollard 的 Rho，还是对不同的分解算法有更好的并行化？

我对组装还很陌生，我正在尝试打印出给定数字的素数分解。经过数小时的网上搜索，我发现了一些关于 DIV 指令的有用花絮，但我无法让我的代码做我想做的事。

我做了一些非常错误的事情，但我无法发现它。请哪位好心人帮我看一下？

实际上，给定 N a（可能非常大）偶数整数，我想找到 N = F * R 其中 gcd(F,R) = 1，F>R，并且 F 尽可能小（因为我将完全因子 F)。问题的核心是找到最大除数 R，其中 R < sqrt(N)。

例如，N=36 应该给出 F=9 和 R=4。请注意，R 不一定是素数或素数幂。请注意，我没有考虑 N。对 F 和 R 的唯一限制是它们是互质的。

这是我的快速和天真的版本，它正在工作：

我想象的另一种方法是按递增顺序查找除数，并在此过程中删除任何非除数的倍数。就像是：

我认为这会很慢并且会占用大量内存，但如果i是生成器，它可能会很有效。我没怎么用过生成器。

我可以改进第一个版本吗？第二个版本可行（我该怎么做）？有没有更好的完全不同的方法？

在 python、c 或伪代码中寻找答案。

这是一个数论课程的项目。我正在实施基于Pocklington的素数测试。虽然我需要一个分解算法，但我们还没有研究过任何算法，而且我可能不会使用诸如二次筛之类的算法，这超出了我的课程范围。我正在就所提出的问题寻求具体帮助。

当按照维基百科上的车轮分解程序进行操作时，我似乎偶然发现了一个问题，如果我尝试构建一个 2-3-5-7 车轮，质数 331 会被视为合数。

带 2-3-5-7 轮，2*3*5*7=210。所以我设置了一个有 210 个插槽的圆圈，并通过步骤 1-7 没有任何问题。然后我到第 8 步，去掉所有素数倍数的辐条，我最终去掉了以 121 为根的辐条，它是 11 的倍数，它是一个素数。对于以 121 为根的辐条，121 + 210 = 331。不幸的是，331 是质数。

维基百科上的程序不正确吗？

还是我误解了程序，应该只删除 2、3、5 和 7 的倍数的辐条，而不是任何其他小于 210 的素数？

为了帮助我学习 Haskell，我正在解决 Project Euler 上的问题。解决每个问题后，我会对照 Haskell wiki 检查我的解决方案，以尝试学习更好的编码实践。这是问题3的解决方案：

我对此的幼稚阅读是primes根据 定义，根据primeFactors定义primes。所以评估primeFactors 9将遵循这个过程：

1. 评估factor 9 primes。
2. 求primes它的第一个元素，即 2。
3. 询问primes它的下一个元素。
4. 作为此过程的一部分，评估primeFactors 3.
5. 求primes它的第一个元素，即 2。
6. 询问primes它的下一个元素。
7. 作为此过程的一部分，评估primeFactors 3.
8. ...

换句话说，步骤 2-4 将无限重复。显然我错了，因为算法终止了。我在这里犯了什么错误？

谁能给我指出一个库/代码，允许我在 python（numpy）中对 Cholesky 分解执行低等级更新？Matlab 将此功能作为一个名为“cholupdate”的函数提供。LINPACK 也具有此功能，但它（据我所知）尚未移植到 LAPACK，因此在 scipy 中不可用。

我发现 scikits.sparse 提供了一个基于 CHOLMOD 的类似函数，但我的矩阵很密集。

是否有任何代码可用于具有与 numpy 兼容的“cholupdate”功能的 python？

谢谢！

我想分解整数，例如

41748850938502584251

我想用蛮力分解这个。鉴于这个数字的长度很短，这应该是可能的。

什么是支持具有任意长度的整数数据类型的合适编程语言？

好的，所以我有一个巨大的数字f。实际上，这个数字只有 100 多位数字。我知道这些因素的大小大致相同。

如果我的资源和时间有限，我应该使用什么语言和算法？我包括在限制时间内对算法进行编码的时间长度。

想法？

编辑：有限，我的意思是在尽可能少的时间内。

有界因子。

给定数 n，判断它是否有任何小于 k 的适当因数。

这是一个co-Np问题吗？