# 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[[1]]] == 0, d[[1]], 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. Dec 18, 2012 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. Dec 19, 2012 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[658]:= \$IterationLimit = Infinity; fd[n_, d_List] := If[Mod[n, d[[1]]] == 0, d[[1]], fd[n, Delete[d, 1]]] In[659]:= e1 = Prime[8000]*Prime[9000]^2; rng = Prime[Range[20000, 1, -1]]; In[661]:= Timing[fd[e1, rng]] Out[661]= {4.630000, 93179} In[662]:= fd2[n_, d_List] := Scan[(If[Mod[n, #] == 0, Return[#]]) &, d] In[663]:= Timing[fd2[e1, rng]] Out[663]= {0.010000, 93179} Dec 19, 2012 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? Dec 20, 2012 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. Dec 18, 2012 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 *)