ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 12 Dec 2018 12:23:20 +0100Lower prime divisorhttps://ask.sagemath.org/question/24969/lower-prime-divisor/ Is there a way in Sage to define the LOWER PRIME FACTOR of n without calculating ALL prime divisors with the list prime_factors(n) ? I would like to make that more quickly
ThanksMon, 24 Nov 2014 15:29:30 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/Comment by slelievre for <p>Is there a way in Sage to define the LOWER PRIME FACTOR of n without calculating ALL prime divisors with the list prime_factors(n) ? I would like to make that more quickly
Thanks</p>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=44651#post-id-44651See also
- [Ask Sage question 44646: Finding factors with Sage](https://ask.sagemath.org/question/44646)Wed, 12 Dec 2018 12:23:20 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=44651#post-id-44651Answer by Luca for <p>Is there a way in Sage to define the LOWER PRIME FACTOR of n without calculating ALL prime divisors with the list prime_factors(n) ? I would like to make that more quickly
Thanks</p>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?answer=24979#post-id-24979It depends on the numbers you are factoring. Factorization algorithms for large numbers do not find factors in increasing order, thus you need to compute all factors in order to know which is smallest.
If your number is small, or has very small factors, this might be fasterâ€¯:
sage: n = 123456789
sage: bound = 100
sage: next(p for p in primes(bound) if n % p == 0)
3
play around with `bound` to find the value that works for you. Be aware that if no prime up to `bound` divides `n`, the last instruction will raise an exception, in that case you can try a higher bound, or use `prime_divisors`.
Mon, 24 Nov 2014 17:59:13 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?answer=24979#post-id-24979Comment by logomath for <p>It depends on the numbers you are factoring. Factorization algorithms for large numbers do not find factors in increasing order, thus you need to compute all factors in order to know which is smallest.</p>
<p>If your number is small, or has very small factors, this might be fasterâ€¯:</p>
<pre><code>sage: n = 123456789
sage: bound = 100
sage: next(p for p in primes(bound) if n % p == 0)
3
</code></pre>
<p>play around with <code>bound</code> to find the value that works for you. Be aware that if no prime up to <code>bound</code> divides <code>n</code>, the last instruction will raise an exception, in that case you can try a higher bound, or use <code>prime_divisors</code>.</p>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24984#post-id-24984Yes, the point is as you say, that factorization algorithms for large numbers do not find factors in increasing order. For lesser n, trial_division(n) suggested by Rolando seems an interesting solution. I wonder up to what value of n...
Thank youMon, 24 Nov 2014 21:04:01 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24984#post-id-24984Answer by Rolandb for <p>Is there a way in Sage to define the LOWER PRIME FACTOR of n without calculating ALL prime divisors with the list prime_factors(n) ? I would like to make that more quickly
Thanks</p>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?answer=24978#post-id-24978There a two ways to avoid calculating all prime divisors. Firstly, look at "trial_division". It gives the first prime divisor.
trial_division(13*97)
13
Secondly, you can use n.factor(limit=yoursearchlimit).
(13*97*191).factor(limit=50)
13 * 18527
Mon, 24 Nov 2014 17:54:19 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?answer=24978#post-id-24978Comment by Luca for <p>There a two ways to avoid calculating all prime divisors. Firstly, look at "trial_division". It gives the first prime divisor.</p>
<pre><code>trial_division(13*97)
13
</code></pre>
<p>Secondly, you can use n.factor(limit=yoursearchlimit).</p>
<pre><code>(13*97*191).factor(limit=50)
13 * 18527
</code></pre>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24980#post-id-24980Didn't know about `trial_division`. It is probably better than my answer, as it does the same thing, but with dedicated code.Mon, 24 Nov 2014 18:00:29 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24980#post-id-24980Comment by slelievre for <p>There a two ways to avoid calculating all prime divisors. Firstly, look at "trial_division". It gives the first prime divisor.</p>
<pre><code>trial_division(13*97)
13
</code></pre>
<p>Secondly, you can use n.factor(limit=yoursearchlimit).</p>
<pre><code>(13*97*191).factor(limit=50)
13 * 18527
</code></pre>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24992#post-id-24992Actually `trial_division` is exactly what you are asking for, if you don't like the name you can do `lower_prime_factor = trial_division` and then call `lower_prime_factor(n)`. You can check the documentation and source code for `trial_division` by doing `a = 3` and then `a.trial_division?` and `a.trial_division??`.Tue, 25 Nov 2014 13:43:56 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24992#post-id-24992Comment by logomath for <p>There a two ways to avoid calculating all prime divisors. Firstly, look at "trial_division". It gives the first prime divisor.</p>
<pre><code>trial_division(13*97)
13
</code></pre>
<p>Secondly, you can use n.factor(limit=yoursearchlimit).</p>
<pre><code>(13*97*191).factor(limit=50)
13 * 18527
</code></pre>
https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24981#post-id-24981The problem is that I look for the lower factor, which I don't know how large can be. So I cannnot impose a search limit. The only thing that I want is that when it find it, it stops searching for the other prime factors. Ok, that can be done by trial_division(n) (thank you for telling me that), but I suppose that it can be much slower than prime_factors(n) for large n.
I hoped that there was something like "lower_primefactor(n)" already in sage... :)Mon, 24 Nov 2014 18:16:21 +0100https://ask.sagemath.org/question/24969/lower-prime-divisor/?comment=24981#post-id-24981