2
$\begingroup$

Is there an easy way to tell Mathematica to find one of the prime factors of $n$ greater than $x$. For example, if $n=1299709\cdot 7919 \cdot 17$, is there a way to request a factor greater than $100$. Please note that I am not interested in finding all factors and filtering the result. My question is about stopping the algorithm as soon as a factor greater than $x$ is found.

Edit: If that capability is not built-in, is there a way to stop the factorization process as soon as one factor is found? There is no assumption about one of the factors being small.


FactorInteger starts with trial division and then moves to Pollard methods, ECM, and MPQS. In principle several of those can deliver a nonprime factor. When the optional second argument is set, I'm not sure if any factor is guaranteed to be prime. – Daniel Lichtblau Sep 30 '14 at 19:11

$\endgroup$
  • 3
    $\begingroup$ FactorInteger[n, k] will stop after k different factors were found $\endgroup$ – Dr. belisarius Sep 30 '14 at 17:32
  • $\begingroup$ Thanks. That definitely answers the edited question. $\endgroup$ – user11356 Sep 30 '14 at 17:33
  • $\begingroup$ It actually answers the question entirely since one of the factors in FactorInteger[n,2] is greater than $x$. $\endgroup$ – user11356 Sep 30 '14 at 17:45
1
$\begingroup$

Factoring algorithms work by finding a prime factor, then dividing by it, then continuing on the result, and so the prime factors are found in essentially random order, unless your algorithm is trial division (which I hope to God mathematica does not use). So, the answer to your question is: filtering is your only solution.

EDIT On the other hand, the OP's request for functionality to return a single prime factor seems quite reasonable (and present, as per @belisarius).

| improve this answer | |
$\endgroup$
  • $\begingroup$ No, it doesn't do it by trial division. The algorithm used in FactorInteger is in fact quite advanced. I modified my question to something that is simpler. $\endgroup$ – user11356 Sep 30 '14 at 17:27
  • 1
    $\begingroup$ I am going to accept this as answer just to close the question as answered. belisarius' reply is, of course, the real answer. $\endgroup$ – user11356 Sep 30 '14 at 18:09
  • 2
    $\begingroup$ FactorInteger starts with trial division and then moves to Pollard methods, ECM, and MPQS. In principle several of those can deliver a nonprime factor. When the optional second argument is set, I'm not sure if any factor is guaranteed to be prime. $\endgroup$ – Daniel Lichtblau Sep 30 '14 at 19:11
  • 1
    $\begingroup$ @DanielLichtblau That is the reason why I haven't posted the comment as an answer $\endgroup$ – Dr. belisarius Oct 1 '14 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy