标签: factorization

我需要得到大数的所有素数因子,这些因子可以很容易地达到1k位.这些数字实际上是随机的,所以它应该不难.我该如何有效地做到这一点？我使用C++和GMP库.

编辑:我猜你们都误解了我.
我的意思是素数是得到数字的所有素因子.
对不起我的英语,在我的语言素数和因素是相同的:)

澄清(来自OP的其他帖子):

我需要的是一种使用C++和GMP(Gnu Multiple Precession lib)有效地计算(找到数字的素数因子)大数(可能达到2048位)的方法,或者更不用说任何其他方式.这些数字实际上是随机的,所以几乎没有机会难以分解,即使这个数字难以计算,我也可以重新编号(尽管不能选择).

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

我试图找到两个因素 - 半数 - 一个非常大的数字.基于我对本文的理解很少,我的假设是,这种并行化在具有许多较小因子的数字上运行良好,而不是在两个非常大的因素上.

这是真的？我应该使用此并行化还是使用其他东西？我是否应该使用Pollard的Rho,还是更好地并行化不同的分解算法？

对于给定数n(我们知道n = p ^ a*q ^ b,对于一些素数p,q和一些整数a,b)和给定数量φ(n)(http://en.wikipedia. org/wiki/Euler%27s_totient_function)找到p,q,a和b.

捕获的是n,并且φ(n)具有大约200个数字,因此算法必须非常快.这似乎是非常难的问题,我完全不知道如何使用φ(n).

怎么解决这个问题？

我有这个问题,这需要解决X在AX=B.A是15000 x 15000的顺序,是稀疏和对称的.B是15000 X 7500并且不稀疏.解决X的最快方法是什么？

我可以想到两种方式.

1. 最简单的方式, X = A\B

2. 使用for循环,

   invA = A\speye(size(A))
   for i = 1:size(B,2)
       X(:,i) = invA*B(:,i);
   end
   

   Run Code Online (Sandbox Code Playgroud)

有没有比上面两个更好的方法？如果没有,我提到的两者之间哪一个最好？

在课堂上我们发现了这个编程问题,目前我们还不知道如何解决它.

n给出正整数.众所周知n = p * q,在哪里p和q是素数,p<=q以及|q-k*p|<10^5某些给定的正整数k.你必须找到p并且q.

输入:

35 1
121 1
1000730021 9

输出:

5 * 7
11 * 11
10007 * 100003

这不是家庭作业,我们只是想解决一些有趣的问题.如果您有一些想法,请在这里发布,以便我们可以尝试一下,谢谢.

为了好玩,我一直用C++实现一些数学习题,而且我一直在尝试实现Fermats Factorisation Method,但是,我不知道我理解它应该返回什么.我有这个实现,返回105维基百科文章中给出的示例号5959.

维基百科中的伪代码如下所示:

一个尝试a的各种值,希望这是一个正方形.

FermatFactor(N): // N should be odd
    a ? ceil(sqrt(N))
    b2 ? a*a - N
    while b2 isn't a square:
        a ? a + 1    // equivalently: b2 ? b2 + 2*a + 1
        b2 ? a*a - N //               a ? a + 1
    endwhile
    return a - sqrt(b2) // or a + sqrt(b2)

我的C++实现,如下所示:

int FermatFactor(int oddNumber)
{
    double a = ceil(sqrt(static_cast<double>(oddNumber)));
    double b2 = a*a - oddNumber; …

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

我试图 在项目Euler上找到问题3指定的数字600851475143的素因子(它要求最高的素因子,但我想找到所有这些因素).但是,当我尝试运行此程序时,我没有得到任何结果.这与我的程序花费多长时间,甚至数字本身有什么关系？

另外,有哪些更有效的方法可以解决这个问题,你有什么建议可以解决这些更优雅的解决方案,因为我正在解决这个问题吗？

一如既往,谢谢!

我正在寻找R中的NMF(非负矩阵分解)的封装/ if-possible-related-off-the-shelf解决方案,它可以处理缺失值(NA)并且不将它们视为0.

事实上,对于一个简单的推荐系统,目标是通过因子分解的产品来估计这些缺失值.

NMF CRAN-package非常棒,但似乎无法做到这一点(它最近的续集也不能用于CRAN),而且我找不到合适的替代包...

是否有算法可以找到整数的所有因子分解,最好是在Python/Java中,但欢迎任何反馈.

我有一个算法来计算素因子.例如[2,2,5]是主要因素20.

def prime_factorization(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n /= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

我还有一个算法来计算算法的所有因子(素数和非素数).例如,因素20是[1, 2, 4, 5, 10, 20].

def factors(n):
    a, r = 1, [1]
    while a * a < n:
        a += 1
        if n % a: continue
        b, f = 1, []
        while n % a == 0: …

我有一个问题,返回一个两个变量的元组v,wt其中vhas shape=(20,20)和wthas shape=(1,).wt是一个重量值的变量.我想在一个内部返回元组(v,wt)map_fn

我的代码看起来有点接近这个

tf.map_fn(fn, nonzeros(Matrix, dim, row))

nonzeros(Matrix, dim, row) returns a (index, value)

该fn会返回一个元组,但错误输出我得到的是:

ValueError: The two structures don't have the same number of elements. First 
structure: <dtype: 'int64'>, second structure: (<tf.Tensor 
'map_2/while/while/Exit_1:0' shape=(20,) dtype=float32>, <tf.Tensor 
'map_2/while/Sub:0' shape=() dtype=int64>).