Prime Factorization as a Nested List

Helmut Knaust, Department of Mathematical Sciences, UTEP, El Paso TX 79968
hknaust@utep.edu
03/05/2014

Flowchart for the Algorithm

p1="p=2\nx=(Subscript[x, 0])";p2="x divisible by p?";p4="x divisible by p?";p5="Save p\n\nx->x/p\np->p\n\nx=1?";p6="x->x\np->next prime";p8="Stop";
LayeredGraphPlot[{p1->p2,{p4->p5,"Yes"},{p4->p6,"No"},{p5->p8,"Yes"},{p5->p4,"No"},p6->p4},Left,BaseStyle->{"Bold",18},VertexLabeling->True,MultiedgeStyle->0.15,ImageSize->{900,400},PlotStyle->Thick]

The Basic Commands

Test[{x_,y_,z_}]=If[Mod[x,Prime[y]]==0,{x/Prime[y],y,Prime[y]},{x,y+1,1}]

The output consists of triples {x,y,z}. x is the number that remains to be factored (the dividend); y stands for the y’th prime number (the divisor); z shows the divisor if the y’th prime divides x, and a ‘1’ otherwise.

NestWhileList[Test,{110,1,1},Function[s,s[[1]]≠1]]

Selecting the Prime Factors and Checking

fact=Select[NestWhileList[Test,{110,1,1},Function[s,s[[1]]≠1]][[All,3]],Function[t,t≠1]]

Apply[Times,fact]

Apply[CenterDot,fact]

Print[Apply[Times,fact]," = ",Apply[CenterDot,fact]]

Converting to a Module

primefact[x_]:=Apply[CenterDot,Select[NestWhileList[Test,{x,1,1},Function[s,s[[1]]≠1]][[All,3]],Function[t,t≠1]]]

primefact[11242420]

prfact[n_]:=Module[{Test},Test[{x_,y_,z_}]=If[Mod[x,Prime[y]]==0,{x/Prime[y],y,Prime[y]},{x,y+1,1}];Apply[CenterDot,Select[NestWhileList[Test,{n,1,1},Function[s,s[[1]]≠1]][[All,3]],Function[t,t≠1]]]]

prfact[170]

The command will still run even if we change the definition of Test.

Test[{x_,y_,z_}]=x+y+z

Test[{1,2,3}]