问题标签 [factorization]

我开发了一种算法来查找给定数字的因子。因此，它还有助于确定给定数字是否为素数。我觉得这是寻找因子或素数的最快算法。

该算法确定给定数字是否在 5*N 的时间范围内是素数（其中 N 是输入数字）。所以我希望我可以称之为线性时间算法。

如何验证这是否是可用的最快算法？有人可以帮忙吗？（比 GNFS 和其他已知的更快）

算法如下

请提供您的意见.. 不要犹豫与我联系以获取更多信息。

谢谢，Harish http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

所以我只想找到给定数字的所有除数（数字本身除外）。目前，我有这个：

其中 primes 是一个素数列表（假设它是正确的，并且足够大）。该算法的工作原理是它找到所有主要因素，但不是所有因素（即给定 34534，它返回 {1,2,17267,31,1114} 但错过 {62, 557} 因为 62 是一个组合，因此也错过了 557。

我也尝试过获取一个数字的主要因素，但我不知道如何将其转换为所有正确组合的列表。

该算法的代码如下：

关于如何修复第一个或如何从第二个创建组合列表的任何想法（我更喜欢这样，因为它会更快）？

可能重复：
有效地找到一个数字的所有除数

这比一般的“找到一种方法”更像是一个效率问题，但是在得到一些奇怪的结果之后，我想看看是否有人可以告诉我为什么最后一种方法效率如此之低：

方式1：蛮力，无优化

方式2：和以前一样，但是这一次，首先检查它的素数（因为这些情况占用的时间最多，使用miller-rabin进行素数检查）

它认为迄今为止最快的方式是方式 3，因为它减少了每次找到质数时使用的数量，并且它只尝试质数（这些是在运行时由筛子生成的，大约需要 34 ms 得到所有小于一百万的素数）这种方式要做的最后一件事是取素数及其幂，并列出所有因数。

方式3：

考虑前一百万个数字所花费的时间：方式 1：7223 毫秒方式 2：8985 毫秒（我猜对于小数字来说，质数检查不值得）方式 3：49423 毫秒

所以我的问题是双重的：1）为什么方式3这么慢？？？2）有什么东西可以让它更快吗？顺便说一句，素数被计算为一个列表，然后转换为一个数组，因为我认为这样会更快。不好的举动？

编辑：

谢谢@yoda 和@morispaa。你是对的，@morispaa 的解决方案有效，即我对转换系数的处理，它基于对Z跨越的空间的假设，以及Z向量的顺序和“方向”，如果我更新Q的列的符号，使得R的对角线具有正元素。

有关我正在进行的转换的更多详细信息，您可以阅读此内容；下面的Z = 采样的 Zernike 多项式，众所周知，它在离散情况（我们的情况）上既不正交也不完整。

关于@morispaa 提出的解决方案为何有效的直觉。我很想听听您对此的意见：

我的直觉是，以某种方式在R中强制执行真正的非负对角线会呈现一个基Q ，它与Z中的向量更好地“对齐” （正如我之前所说，它是非单一的），因此下面的选项 1 和 2，即使它们代表不同的变换，输出系数也可能在相似的空间中。

更具体地说，我认为Z “几乎”是单一的，也许这会导致QR分解返回一个足够接近Z的基础？只有这样，我才能想象我对转换系数的处理（基于对Z中向量的具体情况的假设）在Q的对角线完全为正时起作用，但在它具有负条目时不起作用。你怎么看？

背景

我的机器上安装了 MATLAB R2011a和R2010b。

从R2010b到R2011a的更改之一会影响（请参阅此处qr()有关此特定更改的发行说明）的实施。

我的项目中的一个重要部分qr()用于估计直接和逆变换的正交基。我的代码将此转换应用于输入信号，处理转换后的系数并返回处理后的信号。换句话说，在R2011a中qr()所做的更改使处理此变换的系数的块停止工作（逆变换不会返回已处理信号的预期逆变换）。

不知何故，现在返回的Qqr()矩阵与旧版本不同，这会阻止对变换系数的处理正常工作。

第一个问题

鉴于上述情况，是否可以告诉R2011aqr()从R2010b使用？

第二个问题

我使用Q和Q'来计算直接和逆变换；您可以在此处查看更多详细信息。更具体地说，我使用y = Q * x和x = Q' * y分别计算直接和逆变换。计算直接变换的另一种方法是使用最小二乘法。换句话说，我们有两个选择：

选项 1：使用 QR 分解的直接和逆变换：

选项 2：通过最小二乘拟合进行直接和逆变换

我们的变量是：

在R2011a中，上面的选项 1停止工作（它在R2010b中工作）。我真的很喜欢使用直接和逆变换的想法qr()（它比为每个新向量计算最小二乘要快得多）。如果我想在qr()我的项目中使用新的，有人知道如何使用新的Q使我的转换再次工作吗？

我开始研究计算复杂性、BigOh 表示法等，我的任务是做一个整数分解算法并确定它的复杂性。我已经编写了算法并且它正在工作，但是我在计算复杂度时遇到了麻烦。伪代码如下：

我认为我试图做的事情是非常错误的：

f(x) = n-1 + n-1 + 1 + 1 = 2n

所以

f(n) = O(n)

我认为这是错误的，因为分解算法应该是计算困难的，它们甚至不能是多项式的。那么你有什么建议可以帮助我？也许我在晚上的这个时候太累了，我把这一切都搞砸了:(

先感谢您。

此实现源自 CLRS 第 2 版（第 894 页）。while(1)在我看来很可疑。while 循环的终止条件应该是什么？

我试过k<=n了，但这似乎不起作用。我得到分段错误。代码中的缺陷是什么以及如何纠正它？

我可以得到一个数字的素数，但在代码中，

假设一个数字是 21，所以我得到 1,3,7,0,0，因为我决定数组的范围是 5，我怎样才能擦除 0，使其变为 1,3,7？

我的正常搜索 foo 让我失望了。我试图找到一个返回整数所有因子的 R 函数。至少有 2 个带有factorize()函数的包：gmp 和 conf.design，但是这些函数只返回素数。我想要一个返回所有因素的函数。

显然，搜索这个变得困难，因为 R 有一个称为因子的构造，它在搜索中产生了很多噪音。

我正在设计一种算法来找到作为某个整数 n 中的一个因子存在的最大阶乘数。这个问题在 RGDormey 的“如何通过计算机解决”中给出。你能帮我设计算法吗..答案必须是整数n的一个因子，也是一个阶乘数..

我想到的解决方案：

首先确认整数不是素数。如果素数，没有进一步的解决方案可能..

如果不是素数，找出整数的最大因子

检查它是否是阶乘数..

如果是，那就是答案

如果不是，找出整数的第二大因子..

检查它是否是阶乘数...

等等..

有人可以向我解释一种在 Python（2.7）中找到数字的所有因子的有效方法吗？

我可以创建一个算法来做到这一点，但我认为它的编码很差，并且需要很长时间才能产生大量的结果。