Ask Your Question

factor with a bound

asked 2013-06-25 03:29:04 +0200

anonymous user



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.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2013-06-25 03:48:32 +0200

vdelecroix gravatar image

You can implement a small function

def factorize_small_primes(N,bound):
    res = []                  # list of pairs (prime,multiplicity)
    for p in Primes():
        if p >= bound:
        k = N.valuation(p)    # the nb k such that p^k || N
        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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2013-06-25 03:29:04 +0200

Seen: 367 times

Last updated: Jun 25 '13