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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ FactorInteger[n, k] will stop after k different factors were found $\endgroup$
    – Dr. belisarius
    Commented Sep 30, 2014 at 17:32
  • $\begingroup$ Thanks. That definitely answers the edited question. $\endgroup$
    – user11356
    Commented Sep 30, 2014 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
    Commented Sep 30, 2014 at 17:45

1 Answer 1

Reset to default
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$
4
  • $\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
    Commented Sep 30, 2014 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
    Commented Sep 30, 2014 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
    Commented Sep 30, 2014 at 19:11
  • 1
    $\begingroup$ @DanielLichtblau That is the reason why I haven't posted the comment as an answer $\endgroup$
    – Dr. belisarius
    Commented Oct 1, 2014 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.