# How can I improve this trial division procedure?

My background is procedural programming, so I find this construction quite natural. Is there a way to get rid of the While?

gd[n_, k_] := Block[{d = k + 1}, While[0 != Mod[n, --d]]; d]
gd[n_, d_List] :=
Block[{j = Length[d] + 1}, While[0 != Mod[n, d[[--j]]]]; d[[j]]]

k = 4; n = 25;
gd[n, k]
gd[n, Range[1, k]]
d = Join[{1}, Table[Prime[j], {j, 1, PrimePi[k]}]];
gd[n, d]


My trial division requires the greatest divisor $\leq$ the square root. The $n$ mod $1$ is the terminating step. Whatever the final format, I will need to describe it for a math paper.

Edit The revised functions as recursions:

gd[n_, k_] := If[Mod[n, k] == 0, k, gd[n, k - 1]]
fd[n_, d_List] := If[Mod[n, d[]] == 0, d[], fd[n, Delete[d, 1]]]


Edit The second function as it will be described in my paper:

$$f(n,D)\text{:=} \begin{array}{ll} \lbrace & \begin{array}{ll} n \bmod d_{1}=0 & d_{1} \\ n \bmod d_{1}\neq 0 & f(n,\text{Delete}(D,1)) \\ \end{array} \\ \end{array}$$

• Do you want the greatest proper divisor or the greatest prime divisor? If the former, check for primes beginning at 2 and take the cofactor of the first one that divides your number. If the latter, start at sqrt(n) and work downward, again checking only primes. Either way, precompute your primes and store their differences; that gives you the increment/decrement to use as you go up/down the list. – Daniel Lichtblau Dec 18 '12 at 15:15
• @DanielLichtblau, I put the new functions in the OP. The second one allows me to use a list of divisors, which can be primes or all numbers below the square root. – Fred Kline Dec 19 '12 at 0:35
• A bit long for a comment, but...your fd[] will require both deep recursion/iteration and also has quadratic complexity. Much more efficient to use Map or Scan. I show by way of example. In:= \$IterationLimit = Infinity; fd[n_, d_List] := If[Mod[n, d[]] == 0, d[], fd[n, Delete[d, 1]]] In:= e1 = Prime*Prime^2; rng = Prime[Range[20000, 1, -1]]; In:= Timing[fd[e1, rng]] Out= {4.630000, 93179} In:= fd2[n_, d_List] := Scan[(If[Mod[n, #] == 0, Return[#]]) &, d] In:= Timing[fd2[e1, rng]] Out= {0.010000, 93179} – Daniel Lichtblau Dec 19 '12 at 15:44
• @Daniel I often see unformatted code in your comments. Are you aware that you can wrap the code in backticks to get code? – Mr.Wizard Dec 20 '12 at 12:24

     gd[n_, k_] := If[Mod[n, k] == 0, k, gd[n, k - 1]]

• Very nice! Should be easy to explain in the paper. – Fred Kline Dec 18 '12 at 2:44

Here's a functional way to do the first definition for gd:

f[n_, k_] := NestWhile[# - 1 &, k, Mod[n, #] != 0 &]


I'll leave the second one to you. In general, whenever you encounter repeated application of a particular function, think of Nest (use Fold, for more general cases). Combined with a While loop, you need NestWhile, which is what I used above.

Test this with your function for a bunch of test cases:

With[{list = RandomInteger[{1, 100}, {100, 2}]}, gd @@@ list == f @@@ list]
(* True *)