"Factoring by division" algorithm as described in the book *The Art of Computer Programming*, Vol. 2 by Donald Knuth

Despite the many attempts to draw this simple flowchart, I didn't really know how to do the following:

  1. Drawing a start arrow (as the one before A1)

  2. Drawing an end arrow (as the one after A2 and A7)

  3. Having the structure of the flow between nodes of a diamond shape (as in the arrows connecting A2, A3, A4, and A5)

  4. Drawing a "smart" returning arrow that doesn't penetrate other nodes (as in between A6 and A3)

  5. Adjusting the length of the arrow (or the distance between nodes)

  6. Adjusting the vertical distance between nodes

  7. Putting the diagram in the center

Here is my code:

\usepackage{tikz} % For drawing circles around numbers

\tikzstyle{decision} = [draw, text width=6.0em, text badly centered, node     distance=3cm, inner sep=0pt, minimum height=2.0em]
\tikzstyle{block} = [rectangle, draw, text centered, rounded corners,     minimum height=2.0em]
\tikzstyle{line} = [draw, -latex']
\tikzstyle{cloud} = [draw, ellipse, node distance=3cm, minimum height=2em]

\begin{tikzpicture}[node distance = 2cm, auto]
    % Place nodes
    \node [decision] (init) {Initialize};
    \node [block, below of=init] (trivial) {$N = 1$?};
    \node [decision, right of=trivial] (divide) {Divide};
    \node [decision, below of=divide] (factorFound) {Factor found};
    \node [block, right of=divide, node distance=3cm] (zeroRem){Zero remainder?};
    \node [block, right of=zeroRem, node distance=3cm] (lowQuot)
          {Low quotient?};
    \node [decision, below of=lowQuot] (prime) {$N$ is prime};
    % Draw edges
    \path [line] (init) -- (trivial);
    \path [line] (trivial) -- node {No}(divide);
    \path [line] (divide) -- (zeroRem);
    \path [line] (zeroRem) -- node {No}(lowQuot);
    \path [line] (zeroRem) -- node {Yes}(factorFound);
    \path [line] (factorFound) -- (trivial);
    \path [line] (lowQuot) -- (prime);
    \path [line] (lowQuot) |- node {No}(divide);
    \caption{Trial division as described in [Knuth 2004].}

3 Answers 3


You can use positioning library and control the positioning as you wish.

\usepackage{tikz} % For drawing circles around numbers

decision/.style = {draw, text width=6.0em, text badly centered, node     distance=3cm,  minimum height=2.0em},
block/.style = {rectangle, draw,text width=6.0em, text centered, rounded corners=2ex,     minimum height=2.0em},
line/.style = {draw, -latex'},
cloud/.style = {draw, ellipse, node distance=3cm, minimum height=2em}

\begin{tikzpicture}[node distance = 2cm, auto]
    % Place nodes
    \coordinate (a) at (0,0);
    \node [decision,below = .8cm of a]  (init) {A1. Initialize};
    \node [block, below = .8cm of init] (trivial) {A2. $N = 1$?};
    \node [decision, above right = .15cm and .8cm of trivial] (divide) {A3. Divide};
    \node [decision, below  = .8cm of divide] (factorFound) {A5. Factor found};
    \node [block, below right = .15cm and .8cm of divide, node distance=3cm] (zeroRem){A4. Zero remainder?};
    \node [block, right = .8cm of zeroRem, node distance=3cm] (lowQuot)
          {A6. Low quotient?};
    \node [decision, below = .8cm of lowQuot] (prime) {A7. $N$ is prime};
    % Draw edges
    \path [line] (a) -- (init);
    \path [line] (init) -- (trivial);
    \path [line] (trivial.10) -- node[near end,below=.5ex] {No}(divide.180);
    \path [line] (divide.0) -- (zeroRem.170);
    \path [line] (zeroRem) -- node {No}(lowQuot);
    \path [line] (zeroRem.190) -- node {Yes}(factorFound.0);
    \path [line] (factorFound.180) -- (trivial.-10);
    \path [line] (lowQuot) -- (prime);
    \path [line,rounded corners=7ex] (lowQuot) -- ++(0, 2.5cm) node[right, near start] {No} -| (divide.north);
    %\path [line, near start] (lowQuot) edge[bend right, in=-90, out = -90,] node [near start,right] {No} (divide.north);
    \path [line] (trivial.south) -- +(0,-.8cm);
    \path [line] (prime.south) -- +(0,-.8cm);
    \caption{Trial division as described in [Knuth 2004].}

enter image description here


\matrix is something I always like to promote for these kinds of diagrams:

  > = angle 60,
    matrix of nodes,
    row sep=1.5em,
    column sep=1.5em,
    row 2/.style={nodes=rnd},
    row 1 column 2/.style={yshift=-1em},
    row 3 column 2/.style={yshift=1em},
    text width=6em,
    rounded corners=1.5ex

\matrix (mx) [mymx] {
  A1. Initialize & A3. Divide\\
  A2. $n=1$?     &                  & A4. Zero remainder? & A6. Low quotient?\\
                 & A5. Factor found &                     & A7. $n$ is prime\\
{[every edge/.style={draw,->}]
\draw ([yshift=2em]mx-1-1.north) edge (mx-1-1)
  (mx-1-1) edge (mx-2-1)
  (mx-2-1) edge node[midway,right] {Yes} ([yshift=-2em]mx-2-1.south)
  (mx-2-1) edge node[near end,below] {No}  (mx-1-2.west)
  (mx-1-2) edge (mx-2-3)
  (mx-2-3) edge node[near start,below] {Yes} (mx-3-2)
           edge (mx-2-4)
  (mx-2-4) edge[out=90, in=60] (mx-1-2)

enter image description here

  • 4
    What? No \bye at the end?
    – percusse
    Oct 29, 2013 at 11:18
  • @percusse: heh, tikz doesn't like plain and align=center.
    – morbusg
    Oct 29, 2013 at 11:19
  • Missing a couple of arrows? Oct 29, 2013 at 11:47
  • @Benjamin: those are left as an exercise; there should be enough info in the answer .
    – morbusg
    Oct 29, 2013 at 12:20
  1. \path [line] (init) +(0cm, 1.5cm) -- (init);
  2. \path [line] (prime) -- +(0cm, -1.5cm);
  3. \node [decision, right of=trivial, yshift=1cm] (divide) {Divide};

    \node [decision, below of=divide, node distance=2cm] (factorFound) {Factor found};

    \node [block, right of=trivial, node distance=6cm] (zeroRem){Zero remainder?};

    You might also want to use (factorFound.west) instead of (factorFound) etc. when drawing the arrows to make sure they start at the vertical center of these blocks.

  4. \path [line] (lowQuot) |- ++(0, 1cm) node[right, near start] {No} -| (divide);
  5. It depends. node distance can be given as default for the whole picture but also for each individual node, also there are xshift and yshift aside from manual placement using +(x, y) or ++(x, y)
  6. see 5.
  7. \begin{figure} \centering \begin{tikzpicture} ... \end{tikzpicture} \caption{...} \label{...} \end{figure}, never put the figure environment inside a \begin{center} ... \end{center} environment!

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .