I have finally managed to load a large (more than 13,000,000 digits) into Sage with the help of the people on this forum. I need to factor it and my computer has been running the factor() command for more than 3 hours. I have a fairly ordinary Windows 11 computer. I know the number has no prime factors greater than 101. Is there something better I can do to get the prime factors?
If you want to know exponents for primes in whatever finite set, then valuation() function can do that for you. In your example, knowing that the number has no prime factors greater than 101, one can get factorization of such number N as
L = [ (p,d) for p in primes(2,102) if (d:=valuation(N,p)) > 0 ]The list L here contains pairs (prime, exponent) for all primes ≤101 dividing N. If one wants an actual Factorization object for N, then it can be obtained as
Factorization( L )Thank-you for answering, this looks like exactly what I need, but I'm getting an error. I'm not a programmer so I've probably replaced your variables with my data incorrectly. I tested with:
Sage: n=1755175249584221158925 Sage: L = [ (p,d) for p in primes(5,7,11) if (d:=valuation(N,p)) > 0 ]
and I get: TypeError: unable to coerce <class 'function'=""> to an integer
I checked type of n with: sage: type(n) and got: <class 'sage.rings.integer.integer'="">
In your code you have n but my example uses N. Variable names are case sensitive.
Actually, their code uses both n and N; I think it's the use of N in valuation(N,p) which causes the problem. Anyway, use either n throughout or N throughout, don't mix them.
Use either for p in (5, 7, 11) or for p in primes(5, 12) instead of for p in primes(5, 7, 11).
Thanks, that was stupid of me. So now I tested with:
Sage: N=1755175249584221158925
Sage: L = [ (p,d) for p in primes(5,7,11) if (d:=valuation(N,p)) > 0 ]
and it's waiting for another command.
Sage: Factorization(L) gives
5^2
which is obviously incomplete
The factor method takes an algorithm keyword; have you looked at the documentation?
In your case, since you know that the number of prime factors isn't very large, you could check (if a is your number) whether
p.divides(a)is true, and while it's true, do a.divide_knowing_divisible_by(p). It might be worth seeing how fast those operations are with your number.
Edit:
something like (untested):
b = a
# primes up to 101:
divisors_list = primes_first_n(26)
# keep track of how many times each prime divides a:
divisibility_indices = {p: 0 for p in divisors_list}
for p in divisors_list:
while p.divides(b):
divisibility_indices[p] += 1
b = b.divide_knowing_divisible_by(p)
print(divisibility_indices)Thanks for responding. I don't think this really gives me what I need as I don't know that every single prime up to 101 divides the number, and even if it does I don't know how many times. I've tested this command and it's not obvious when the prime I use doesn't divide it, it just rounds.
First, I suggested first checking whether p.divides(a) before dividing. Second, I've provided some untested code to keep track of how many times each prime divides the number.
Thanks for the code. It worked on a small number but ran all day without producing a result on my large number. I think maybe my computer isn't up to this.
Asked: 0 years ago
Seen: 84 times
Last updated: Mar 11
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.