# How to produce a list of prime numbers in LaTeX

I would like to write a LaTeX script that produces all the prime numbers between the numbers n and m, where n < m. How can I do this? I feel it shoud not be that hard, but I cannot seem to program it.

-
What's the formula? .....:) Related tex.stackexchange.com/questions/44673/… – percusse Sep 20 '13 at 18:07
@percusse I see... maybe the $n<m$ sign covered up the rest, but I assure you that I added nothing to the OP's question. – Andrea L. Sep 20 '13 at 18:11
@AndreaL. oh no, no problem, just curious – percusse Sep 20 '13 at 18:13
I suspect that the <m was being interpreted as the start of an HTML tag and so being removed since HTML tags aren't allowed in posts. Once it was in an inline code then it was obviously no longer a tag and the SE formatter no longer removed it. – Loop Space Sep 20 '13 at 18:25
@kevin is LuaLaTeX allowed? – Loop Space Sep 20 '13 at 18:26

\documentclass{article}
%
\makeatletter
\def\primes#1#2{{%
\def\comma{\def\comma{, }}%
\count@\@ne\@tempcntb#2\relax\@curtab#1\relax
\@primes}}
\expandafter\ifx\csname p-\the\count@\endcsname\relax
\ifnum\@tempcntb<\count@\else
\ifnum\count@<\@curtab\else\comma\the\count@\fi\fi\else\repeat
\expandafter\let\csname p-\the\@tempcnta\endcsname\@ne
\ifnum\@tempcnta<\@tempcntb\repeat
\ifnum\@tempcntb>\count@\expandafter\@primes\fi}
\makeatother
%
\begin{document}

\primes{1}{10}

\primes{1}{100}

\primes{1}{1000}

\primes{900}{1000}

\end{document}

-
you really shouldn't end with a hanging comma. (just being a pest.) – barbara beeton Sep 20 '13 at 20:43
@barbarabeeton I left that for you:-) – David Carlisle Sep 20 '13 at 20:48
@barbarabeeton done:-) – David Carlisle Sep 20 '13 at 21:04
Corrected the typo inside makeatoletter to makeatother, although you deserve +1 for a much better algorithm to calculate primes (I gave up on the answer unfortunately...) – Andrea L. Sep 20 '13 at 21:23
@AndreaL. that algorithm is somewhat older than me:-) – David Carlisle Sep 20 '13 at 21:29

D.E. Knuth has done this himself on page 218 of The TeXbook:

\newif\ifprime \newif\ifunknown % boolean variables
\newcount\n \newcount\p \newcount\d \newcount\a % integer variables
\def\primes#1{2,~3% assume that #1 is at least 3
\n=#1 \advance\n by-2 % n more to go
\p=5 % odd primes starting with p
\def\printp{, % we will invoke \printp if p is prime
\ifnum\n=1 and~\fi % ‘and’ precedes the last value
\def\printifprime{\testprimality \ifprime\printp\fi}
\def\testprimality{{\d=3 \global\primetrue
\def\trialdivision{\a=\p \divide\a by\d
\ifnum\a>\d \unknowntrue\else\unknownfalse\fi
\multiply\a by\d
\ifnum\a=\p \global\primefalse\unknownfalse\fi}

The first 100 prime numbers are \primes{100}

The first 1000 prime numbers are \primes{1000}

\bye


He writes, before providing the above macro:

The first thirty prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113. You may not find this fact very startling; but you may be surprised to learn that the previous sentence was typeset by saying The first thirty prime numbers are \primes{30}. TeX did all of the calculation by expanding the \primes macro, so the author is pretty sure that the list of prime numbers given above is quite free of typographic errors.

-
oh yes,so he does:-) +1 but I prefer Eratosthenes to trial division:-) – David Carlisle Sep 20 '13 at 21:07
the text accompanying this demonstration (in the texbook) mentions a restriction that some people think is a design flaw, namely that loops cannot be nested without supplying an extra grouping level. sit user cavete. – barbara beeton Sep 20 '13 at 21:14

This solution exploits \pgfmathisprime macro provided by Alain Matthes' tkz-euclide package.

\documentclass{article}
\usepackage{tkz-euclide}

\newif\ifcomma

\newcommand{\primes}[2]{%
\commafalse%
\foreach\numb in {#1,...,#2}{%
\pgfmathisprime{\numb}%
\ifnum\pgfmathresult=1
\ifcomma, \numb\else\numb\global\commatrue\fi%
\fi%
}%
}

\begin{document}

\primes{1}{10}

\primes{1}{100}

\primes{1}{1000}

\primes{900}{1000}

\end{document}


-
Be careful with these commands because now they are included in pgf 2.10 cvs and pgf 3.0 You can find : isprime, iseven and isodd. – Alain Matthes Feb 3 '14 at 10:04
@AlainMatthes Does your comment mean: 1) the above solution won't work anymore. 2) There will be an easier solution? – karlkoeller Feb 3 '14 at 10:55
If my code is correct in tkz-euclide then there is no problem. I have not worked with PGF 3 and I have not worked on my codes for a few months ... In principle, if these new commands are defined then those of my package are not loaded – Alain Matthes Feb 3 '14 at 11:06

Perhaps you want an expandable macro, which one can use inside an \edef? Here is a way to do it using \xintiloop of xinttools.

And expandability also means one writes primes to the log as simply as \typeout {\PrimeList {0}{10000}}. And it also facilitates building up tables, as is examplified in this update.

The update has a slightly different way to handle the expandable handling of the separator, it is a bit more efficient and lean, but the separator is not authorized to be empty; maybe a space, no problem, but not strictly empty.

nota bene I use \xintiloop because essentially the code was already done in the xint manual, so some work was spared. But I put some additional effort to get a two parameter macro not assuming its inputs to be ordered and also using an intelligent prime separator (here a comma and a space, customizable), which does not show at the very end.

% EXPANDABLY computing the sequence of primes p with n<= p<= m

\documentclass{article}
\usepackage{xinttools}

\makeatletter
\long\def\@gobblethree #1#2#3{}% thought that was in the kernel already...
% xinttools has \xint_gobble_iii but
% let's not scare people with \catcode_ 11

% can be customized
% Nota Bene: must NOT be empty (can be a space, or a single character, but must
% not be empty) (the expandable cancellation of
% pre-/post-separator is handled in a more efficient way which however is not
% compatible with an empty separator)
\newcommand{\PrimeSeparator}{, }

\newcommand{\PrimeList}[2]{%
\expandafter\Primes@a\the\numexpr #1\expandafter.\the\numexpr #2.%
}

\def\Primes@a #1.#2.{\ifnum #2<2 \expandafter\@gobblethree
\else
\ifnum #1>#2
\expandafter\expandafter\expandafter\@gobblethree
\fi\fi
\Primes@b {#1}{#2}}

\def\Primes@abort@b\fi #1\fi #2#3.#4.{\fi }

\def\Primes@b #1#2{\ifnum #2=2 2\Primes@abort@b\fi
\ifnum #1<3 2\expandafter\@firstoftwo
\else\expandafter\@secondoftwo
\fi
{\Primes@c 3}
{\expandafter\Primes@GobFirstSep
\romannumeral-0\expandafter\Primes@c
\the\numexpr 2*((#1-1)/2)+1}%
.#2.}

% 3<= #1 odd  but if #1=#2=2n initially, then now #1>#2
%
\def\Primes@abort@c\fi #1.#2.{\fi \space\Primes@GobFirstSep}

\def\Primes@c #1.#2.{\ifnum #1>#2 \Primes@abort@c\fi
\expandafter\Primes@d\the\numexpr 2*(#2/2)-1.#1.}

\def\Primes@d #1.#2.{% here #2 is odd start and #1 odd finish, #1>=#2
\xintiloop [#2+2]
{\xintiloop [3+2]
\ifnum\xintouteriloopindex<\numexpr\xintiloopindex*\xintiloopindex\relax
\PrimeSeparator\@gobble\Primes@GobFirstSep\xintouteriloopindex
\expandafter\xintbreakiloop
\fi
\ifnum\xintouteriloopindex=\numexpr
(\xintouteriloopindex/\xintiloopindex)*\xintiloopindex\relax
\else
\repeat
}% no space here
\ifnum \xintiloopindex <#1 \repeat
}

% PrimeSeparator ne doit pas être vide, au minimun un espace
\def\Primes@GobFirstSep #1\Primes@GobFirstSep {}

\makeatletter

\newcommand{\nbColumns}{10}
\newcounter{cellcount}

\newcommand{\SetUpSeparatorForTabular}
{\setcounter{cellcount}{1}%
\renewcommand\PrimeSeparator
{\ifnum\nbColumns=\value{cellcount}%
\expandafter\@firstoftwo
\else\expandafter\@secondoftwo
\fi {\\\setcounter{cellcount}{1}}
{&\stepcounter{cellcount}}}%
}

\begin{document}\thispagestyle{empty}
%\PrimeList{0}{1000}

\typeout {\PrimeList {1000}{2000}}% go see the log!

\begin{table}[!htbp]
\centering
\caption{\strut The primes between 2000 and 3000}
\renewcommand{\nbColumns}{11}
\SetUpSeparatorForTabular
\begin{tabular}{*{\nbColumns}c}
\hline
\PrimeList {2000}{3000}
\\\hline
\end{tabular}
\end{table}

\begin{table}[!htbp]
\centering
\caption{\strut The primes between 20000 and 21000}
\renewcommand{\nbColumns}{7}
\SetUpSeparatorForTabular
\begin{tabular}{*{\nbColumns}c}
\hline
\PrimeList {20000}{21000}
\\\hline
\end{tabular}
\end{table}
\end{document}


It is obviously very useful to have such an expandable macro, so here is the code:

% Expandably computing a sequence of consecutive primes.

\documentclass{article}
\usepackage{xinttools}

\makeatletter
\long\def\@gobblethree #1#2#3{}% thought that was in the kernel already...
\newcommand{\PrimeSeparator}{, }

\newcommand{\PrimeList}[2]{%
\expandafter\Primes@a\the\numexpr #1\expandafter.\the\numexpr #2.%
}

\def\Primes@a #1.#2.{\ifnum #2<2 \expandafter\@gobblethree
\else
\ifnum #1>#2
\expandafter\expandafter\expandafter\@gobblethree
\fi\fi
\Primes@b {#1}{#2}}

\def\Primes@abort@b\fi #1\fi #2#3.#4.{\fi }

\def\Primes@b #1#2{\ifnum #2=2 2\Primes@abort@b\fi
\ifnum #1<3 2\expandafter\Prime@Separator
\romannumeral-0%
\expandafter\@firstoftwo
\else\expandafter\@secondoftwo
\fi
{\Primes@c 3}
{\romannumeral-0\expandafter\Primes@c
\the\numexpr 2*((#1-1)/2)+1}%
.#2.}

% 3<= #1 odd  but if #1=#2=2n initially now #1>#2
\def\Primes@abort@c\fi #1\relax{\fi \space}

\def\Primes@c #1.#2.{\ifnum #1>#2 \Primes@abort@c\fi
\expandafter\Primes@d\the\numexpr 2*(#2/2)-1.#1.\relax}

\def\Primes@d #1.#2.{% here #2 is odd start and #1 odd finish, #2<=#1
\xintiloop [#2+2]
{\xintiloop [3+2]
\ifnum\xintouteriloopindex<\numexpr\xintiloopindex*\xintiloopindex\relax
\xintouteriloopindex
\expandafter\Prime@Separator\romannumeral-0%
\expandafter\xintbreakiloop
\fi
\ifnum\xintouteriloopindex=\numexpr
(\xintouteriloopindex/\xintiloopindex)*\xintiloopindex\relax
\else
\repeat
}% no space here
\ifnum \xintiloopindex <#1 \repeat
}

\def\Prime@Separator #1{\ifx #1\relax\else\PrimeSeparator #1\fi }

\makeatletter

\begin{document}\thispagestyle{empty}
\PrimeList{0}{1000}

\ttfamily

\edef\Z {\PrimeList {1000}{2000}}
\meaning\Z

\end{document}

-

D. E. Knuth also gives a version of his favourite prime number algorithm in The Metafont Book, (p.173), which we can use in Metapost to make a visualization of them related to the Ulam Spiral.

prologues := 3; outputtemplate := "%j%c.eps";
% see D.E.Knuth, The Metafont Book, p.173
numeric p[]; boolean n_is_prime; p[1]=2; k:=1;
for n=3 step 2 until infinity:
n_is_prime := true;
for j=2 upto k:
if n mod p[j]=0: n_is_prime := false; fi
exitif n/p[j] < p[j];
endfor
if n_is_prime: p[incr k] := n; exitif k=62; fi
endfor fi
%
beginfig(1);
draw fullcircle scaled 480 withcolor .673 red;
for r=0 upto 9:
draw fullcircle scaled 2(40+20r) withcolor .7 white;
if r>1: drawarrow origin -- right scaled 240 rotated (12*p[2+r]) withcolor .7 white; fi
endfor
for k=1 upto 62:
label(decimal p[k], right scaled (40 + 20 floor(p[k]/30)) rotated (p[k]*12));
endfor
endfig;
end
`
-