Lower prime divisor

asked 2014-11-24 15:29:30 +0100

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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

edit retag flag offensive close merge delete

Comments

2 Answers

Sort by » oldest newest most voted

answered 2014-11-24 17:54:19 +0100

Rolandb
58 ●6 ●9 ●14

There 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

edit flag offensive delete link

Comments

Didn't know about trial_division. It is probably better than my answer, as it does the same thing, but with dedicated code.

Luca ( 2014-11-24 18:00:29 +0100 )edit

The 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... :)

logomath ( 2014-11-24 18:16:21 +0100 )edit

Actually 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??.

slelievre ( 2014-11-25 13:43:56 +0100 )edit

add a comment

answered 2014-11-24 17:59:13 +0100

Luca
880 ●5 ●21

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.

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.

edit flag offensive delete link

Comments

Yes, 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 you

logomath ( 2014-11-24 21:04:01 +0100 )edit

add a comment

Your Answer

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

Add Answer

Lower prime divisor

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Lower prime divisor edit

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Lower prime divisor