# How to produce a list of prime numbers in LaTeX

14,037

## Solution 1

\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}


## Solution 2

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.

## Solution 3

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}


## Solution 4

warning: this answer focuses 1) on big integers (beyond TeX reach) and 2) on primality testing one number, then lists of primes are obtained by applying the test in succession. For long lists of small integers this is clearly much less efficient than Eratosthenes type of sieving.

As my answer is basically on primality test of one number, it is borderline compared to OP. See @DavidCarlisle and @wipet (and perhaps the other answers too) for Eratosthenes type of approaches.

• since xint 1.2h, there is \xintNewFunction which can be used even for recursive definitions, contrarily to \xintdeffunc. The xint documentation (section 5.3 Miller-Rabin Pseudo-Primality expandably) uses \xintNewFunction which simplifies a bit the syntax compared to the answer here.

The answer here needs the user to define manually recursive TeX macros and to plug them into a \xintexpr genuine function, whereas the approach from current xint manual employs directly the \xintexpr syntax (thanks to \xintNewFunction), thus removing the need for user to define TeX macros (but \xintNewFunction must use #1, #2, ... contrarily to \xintdeffunc which allows user-chosen arbitrary variables x, y, ...).

• Also the code comments below mention a problem with (condition)?{foo}{bar} expanding too early foo; this bug was fixed at xint 1.2h (2016/11/20), so the extra space before foo is not needed anymore.

## Renewed answer: approach via Strong Pseudo Primality tests.

According to http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, it is known, due to extensive computations on SuperComputers how to determine with certainty if a number of at most 24 digits is prime by verifying if it is a strong pseudo-prime for the bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. Actually if we use only 2, 3, 5, 7, we can guarantee that strong pseudo-primality implies primality for N < 3215031751, in particular for all TeX numbers as they are < 2^31 < 3215031751.

I have written an expandable implementation. For TeX numbers, compared to the approach which divides using \numexpr all the way up to the square-root by odd integers, I observed that this becomes competitive for 9 or 10 digits. This is due to the fact that the modular exponentiation is implemented for big integers, if I did a routine entirely in \numexpr I think the strong pseudo-prime approach would be competitive earlier.

Here the code tests strong pseudo-primality for bases 2, 3, 5, 7, 11, 13, 17 which is enough for N < 341,550,071,728,321 which has 15 digits. Hence all 14 digits numbers in particular are correctly handled. Naturally if we tested only 2, 3, 5, 7 this would go faster (in my brief testing, about 25%).

Anyway, if switching to another language with normal access to CPU for computing, divide by a factor 1000 at least the computation times... but Slow Computing has its rewards too.

I started from a Python implementation, and until BLF has written a Python to xintexpr converter, I needed to then code myself in TeX. The code is a bit hacky due to:

1. currently \xintdeffunc does not allow recursivity. I ended up writing modular exponentiation with macros and not in xintexpr syntax (I did obtain the macro via insider user of this syntax, then I simplified it for efficiency). Notice that this modular exponentiation is for big integers, it would be much faster if written only with \numexpr.

2. currently (and possibly ever) \xintdeffunc does not allow some of the syntax with iter, break... one can still define a function usable as such in expressions, but this goes via somewhat hackish detour.

As said above, the code from my earlier answer below handling TeX integers is competitive all the way to 9 or 10 digits with the one here. The one here is much less efficient for smaller numbers. But it allows things like this :

Not to say that it is fast ... recall you can speed up a little by commenting out the lines with 11, 13, 17. Turns out it works also for the first computation to not use 11, 13, 17, but that was not guaranteed.

The code needs xintexpr 1.2g or later (meaning of iter changed in that release).

\documentclass{article}

\usepackage{xintexpr}

% I -------------------------------- Modular Exponentiation

% Currently (xintexpr 1.2g), it is not possible to use \xintdefiifunc like
% this in a recursive manner:

% \xintdefiifunc powmod(x,m,n):=if(m,
%     % m non zero (assume positive), and look if m=1
%     if(m=1, x/:n,
%           if(odd(m), (x*sqr(powmod(x,m//2,n)))/:n,
%                      sqr(powmod(x,m//2,n))/:n))
%     % m is zero, return 1
%     , 1);

% We thus use the macro way
\makeatletter

% #1=x, #2=m, #3=N, compute x^m modulo N (with m non negative)
%
% We will always use it with 1< x < N (in fact with x = 2, 3, 5 ...)
% hence we skip an initial reduction modulo N.

\newcommand*\PowMod [3]{% #1=x, #2=m, #3=N
\xintiiifZero {#2}{1}{\PowMod@a {#1}{#2}{#3}}}

\def\PowMod@a #1#2#3%
{%
\xintiiifOne {#2}
{#1}
{\xintiiifOdd {#2}
{\expandafter\PowMod@odd}
{\expandafter\PowMod@even}%
\expandafter{\romannumeral0\xinthalf{#2}}{#1}{#3}%
}%
}%

\def\PowMod@odd #1#2#3%
{\xintiiMod{\xintiiMul{#2}{\xintiiSqr{\PowMod{#2}{#1}{#3}}}}{#3}}
\def\PowMod@even #1#2#3%
{\xintiiMod{\xintiiSqr{\PowMod{#2}{#1}{#3}}}{#3}}

\makeatother

% II ------------------------------ Miller-Rabin compositeness witness

% ALGORITHM FOR PROOF OF COMPOSITENESS OF AN ODD n

% Write n=2^k m + 1 with m odd and k at least 1

% Choose 1<x<n.
% compute y=x^m modulo n
% if equals 1 we can't say anything
% if equals n-1 we can't say anything
% else put j=1, and
% compute repeatedly the square, incrementing j by 1 each time,
% thus always we have y^{2^{j-1}}
%   -> if at some point n-1 mod n found, we can't say anything and break out
%   -> if however we never find n-1 mod n before reaching
%        z=y^{2^{k-1}} with j=k
%        we then have z^2=x^{n-1}.
% Suppose z is not -1 mod n. If z^2 is 1 mod n, then n can be prime only if
% z is 1 mod n, and we can go back up, until initial y, and we have already
% excluded y=1. Thus if z is not -1 mod n and z^2 is 1 then n is not prime.
% But if z^2 is not 1, then n is not prime by Fermat. Hence (z not -1 mod n)
% implies (n is composite). (Miller test)

% Unfortunately, we can not use iter, break, like below in an \xintdefiifunc.
% But we do want to define a genuine function isCompositeWitness, useable in
% expressions. The trick is to declare a dummy function then define directly
% an associated macro.

% dummy definition
\xintdefiifunc isCompositeWitness(x,n,m,k):=1;
\catcode_ 11
\def\XINT_iiexpr_userfunc_isCompositeWitness #1,#2,#3,#4,%
{\xinttheiiexpr
subs((y==1)?{0}
{iter(y;(j=#4)?{break(!(@==#2-1))}
{(@==#2-1)?{break(0)}{sqr(@)/:#2}},j=1++)}
,y=\PowMod{#1}{#3}{#2})
\relax }
\catcode_ 8

% III ------------------------------------- Strong Pseudo Primes

% cf
%  http://oeis.org/A014233
%     <http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html>

%     <http://mathworld.wolfram.com/StrongPseudoprime.html>

% check if positive integer <49 si a prime.
% 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47
\newcommand*\IsVerySmallPrime [1]
{\ifnum#1=1 \xintdothis0\fi
\ifnum#1=2 \xintdothis1\fi
\ifnum#1=3 \xintdothis1\fi
\ifnum#1=5 \xintdothis1\fi
\ifnum#1=\numexpr (#1/2)*2\relax\xintdothis0\fi
\ifnum#1=\numexpr (#1/3)*3\relax\xintdothis0\fi
\ifnum#1=\numexpr (#1/5)*5\relax\xintdothis0\fi
\xintorthat 1}

% dummy definition
\xintdefiifunc isPseudoPrime(n):= 1;
\catcode_ 11
\def\XINT_iiexpr_userfunc_isPseudoPrime #1,%
{\xinttheiiexpr
(#1<49)?
% there is a bug currently in xintexpr which causes an expansion of
% \foo in situations like (test)?{\foo}{bar}. Sorry about that.
% Putting a space before \foo solves the problem.
{ \IsVerySmallPrime{#1}}
{(even(#1))?
{0}
{subs(
% L expands to two values m, k hence isCompositeWitness does get
% four arguments x, n, m, k (n and m are odd, and n-1=2^k m)
\if1\xinttheiiexpr isCompositeWitness(2, #1, L)\relax\xintdothis0\fi
\if1\xinttheiiexpr isCompositeWitness(3, #1, L)\relax\xintdothis0\fi
\if1\xinttheiiexpr isCompositeWitness(5, #1, L)\relax\xintdothis0\fi
\if1\xinttheiiexpr isCompositeWitness(7, #1, L)\relax\xintdothis0\fi
% above enough for N<3215031751 hence all TeX numbers
\if1\xinttheiiexpr isCompositeWitness(11, #1, L)\relax\xintdothis0\fi
% above enough for N<2152302898747, hence all 12-digits numbers
\if1\xinttheiiexpr isCompositeWitness(13, #1, L)\relax\xintdothis0\fi
% above enough for N<3474749660383
\if1\xinttheiiexpr isCompositeWitness(17, #1, L)\relax\xintdothis0\fi
% above enough for N<341550071728321
\xintorthat 1,
L=iter(#1//2;(even(@))?{@//2}{break(@,k)},k=1++))}}
\relax }
\catcode_ 8

% This macro thus determinates if #1>0 is PseudoPrime with respect to the
% Miller-Rabin test with x=2, 3, 5, 7, 11, 13, 17.
%
% if #1<341550071728321 is declared PseudoPrime, it really is prime
%

\newcommand*\IsPseudoPrime [1]{\xinttheiiexpr isPseudoPrime(#1)\relax}

\begin{document}
% 3.14159265358979323846...

% Smallest prime at least equal to 314159265358979
% The n=X++ syntax requires X to be a TeX integer, hence we can't
% use directly 314159265358979++

The smallest prime number at least equal to 314159265358979 is
\xinttheiiexpr
seq(isPseudoPrime(314159265358979+n)?
{break(314159265358979+n)}{omit}, n=0++)\relax.

% is 314159265359057

The prime numbers between 3 123 456 000 and 3 123 457 000 are:

% please be a bit patient.
% for this you need only the test using primes 2, 3, 5, 7
% there is no need for 11, 13, and 17.

\raggedright

\noindent
\xinttheiiexpr seq(isPseudoPrime(n)?{n}{omit},n=3 123 456 000..[+1]..3 123 457
000)\relax.

\end{document}


## Original Answer: primality testing by attempted factorizations with \numexpr.

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}


## Solution 5

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

Share:
14,037

Author by

### kevin

Updated on October 26, 2020

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 should not be that hard, but I cannot seem to program it.

What's the formula? .....:) Related tex.stackexchange.com/questions/44673/…
@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.
@AndreaL. oh no, no problem, just curious
@percusse maybe it's an internal bug regarding the question code here on this site (I know why the OP added  to his formula, it's a common use on Math.SX...)
@percusse: When you look at the source of the original post in the edit history, you can see the sentence.
• Andrew Stacey about 10 years
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.
• Andrew Stacey about 10 years
@kevin is LuaLaTeX allowed?
I am surprised that this has been voted up, and people is taking it serious. I am sure that that is just me being judgmental. LaTeX is a typesetting language.
@Hans-PeterE.Kristiansen See the link in the first comment
Possible duplicate of this question too, if you forget about the tikz part.
@Hans-PeterE.Kristiansen, there are people using TeX as a programming language to participate in the ICFP programming contest...
• David Carlisle about 10 years
@Hans-PeterE.Kristiansen do you also query say \rotatebox (which requires calculating sin and cosine in TeX) or pgfplot which requires any amount of calculation or....
• David Carlisle about 10 years
@AndrewStacey no:-)
• Andrew Stacey about 10 years
@DavidCarlisle I asked for "allowed", not "required"!
can one cheat a little? latex(sym(primes(10))) gives \left(\begin{array}{cccc} 2 & 3 & 5 & 7 \end{array}\right) using Matlab :)
• barbara beeton about 10 years
you really shouldn't end with a hanging comma. (just being a pest.)
• David Carlisle about 10 years
@barbarabeeton I left that for you:-)
• David Carlisle about 10 years
@barbarabeeton done:-)
• David Carlisle about 10 years
oh yes,so he does:-) +1 but I prefer Eratosthenes to trial division:-)
• barbara beeton about 10 years
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.
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...)
• David Carlisle about 10 years
@AndreaL. that algorithm is somewhat older than me:-)
• Alain Matthes almost 10 years
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.
• karlkoeller almost 10 years
@AlainMatthes Does your comment mean: 1) the above solution won't work anymore. 2) There will be an easier solution?
• Alain Matthes almost 10 years
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