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.Tue, 25 Jun 2013 03:48:32 +0200factor with a boundhttps://ask.sagemath.org/question/10273/factor-with-a-bound/Hi,
I need to find relatively small prime factors of some big numbers. How do I make factor command working with a bound? For instance let's say I am just interested in prime divisors less than 20 and I want to factor 11891. The answer I want would be 11*1081.
Tue, 25 Jun 2013 03:29:04 +0200https://ask.sagemath.org/question/10273/factor-with-a-bound/Answer by vdelecroix for <p>Hi,</p>
<p>I need to find relatively small prime factors of some big numbers. How do I make factor command working with a bound? For instance let's say I am just interested in prime divisors less than 20 and I want to factor 11891. The answer I want would be 11*1081. </p>
https://ask.sagemath.org/question/10273/factor-with-a-bound/?answer=15134#post-id-15134You can implement a small function
def factorize_small_primes(N,bound):
res = [] # list of pairs (prime,multiplicity)
for p in Primes():
if p >= bound:
break
k = N.valuation(p) # the nb k such that p^k || N
res.append((p,k))
N /= p^k
return Factorization(res + [(N,1)])
And use it as follows
sage: N = 2^3 * 13^5 * 523^2 * 541^3
sage: f = factorize_small_primes(N,20)
sage: f
2^3 * 13^5 * 43310697015709
You can also check that the answer is somewaht consistent
sage: f.expand() == N
True
Tue, 25 Jun 2013 03:48:32 +0200https://ask.sagemath.org/question/10273/factor-with-a-bound/?answer=15134#post-id-15134