Add a function to return integer factorization

[certik]

Here is the API that I would imagine:

std::vector<int> factors;
primesieve::factor(1001, &factors);

which would put the numbers 7, 11, 13 into factors. I am sure you would know the fastest way to do that using your library.

That would be consistent with the current API for the generate_primes function:

std::vector<int> primes;
primesieve::generate_primes(1000, &primes);

[kimwalisch]

Hi Ondřej,

Thanks for your feedback. I like the design philosophy of UNIX which says a program should do only one thing and do it well. primesieve generates primes using a prime sieve but factoring requires fundamentally different algorithms so I think that you should use a separate library for this e.g. FLINT, GMP-ECM, msieve or yafu. Also I think that writing a very fast integer factorization function that runs on all operating systems and CPUs is a non-trivial task (yafu's SQUFOF code is 1100 lines, and there are over 2500 lines of support code for factoring.).

Regards, Kim

[certik]

Hi Kim, it makes sense. So I guess primesieve is the tool to get the prime numbers, that's it. And then I should write me own function that uses those to factor integers. I tried to use GMP-ECM first, but it fails sometimes (if you just use ecmfactor), so that led me to the search for robust ways to factor integers and that's how I found your library. See e.g. this thread where my problems are explained in detail: https://groups.google.com/d/topic/sage-devel/-mslmcxskUs/discussion

So I am closing this issue. I am just looking for some BSD style licensed (preferably) library for factorization. For now I'll use your library to get the primes and then just trial division. That should get me started for most integers that people might need in practice, for the CSymPy library, that we've been developing. Later I might use some specialized library just for factorization. I just need something robust, reasonably simple to maintain and as fast as it can be for now. Your library seems one of the fastest to get the primes, so that's the foundation. Let me know if you have any feedback regarding that.

[kimwalisch]

Hi Ondřej,

I am just looking for some BSD style licensed (preferably) library for factorization.

Please have a look at the FLINT library (http://flintlib.org/) which offers fast integer factorization.

FLINT Features (http://www.flintlib.org/features.html):

• Fast factorisation (trial division, Hart's one line algorithm, SQUFOF)
• qsieve - small quadratic field Efficient factorisation of integers up to two words (64 or 128 bits)

It is GPLv2 licensed though. I am not aware of any BSD licensed factoring library.

Regards, Kim

On Fri, Jan 31, 2014 at 6:39 PM, Ondřej Čertík notifications@github.comwrote:

Hi Kim, it makes sense. So I guess primesieve is the tool to get the prime numbers, that's it. And then I should write me own function that uses those to factor integers. I tried to use GMP-ECM first, but it fails sometimes (if you just use ecmfactor), so that led me to the search for robust ways to factor integers and that's how I found your library. See e.g. this thread where my problems are explained in detail: https://groups.google.com/d/topic/sage-devel/-mslmcxskUs/discussion

So I am closing this issue. I am just looking for some BSD style licensed (preferably) library for factorization. For now I'll use your library to get the primes and then just trial division. That should get me started for most integers that people might need in practice, for the CSymPyhttps://github.com/certik/csympylibrary, that we've been developing. Later I might use some specialized library just for factorization. I just need something robust, reasonably simple to maintain and as fast as it can be for now. Your library seems one of the fastest to get the primes, so that's the foundation. Let me know if you have any feedback regarding that.

— Reply to this email directly or view it on GitHubhttps://github.com/kimwalisch/primesieve/issues/3#issuecomment-33824159 .