How to produce a list of prime numbers in LaTeX

Question

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.

Answer 1

\documentclass{article}
%
\makeatletter
\def\primes#1#2{{%
  \def\comma{\def\comma{, }}%
  \count@\@ne\@tempcntb#2\relax\@curtab#1\relax
  \@primes}}
\def\@primes{\loop\advance\count@\@ne
\expandafter\ifx\csname p-\the\count@\endcsname\relax
\ifnum\@tempcntb<\count@\else
  \ifnum\count@<\@curtab\else\comma\the\count@\fi\fi\else\repeat
\@tempcnta\count@\loop\advance\@tempcnta\count@
\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}

Answer 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
\loop\ifnum\n>0 \printifprime\advance\p by2 \repeat}
\def\printp{, % we will invoke \printp if p is prime
\ifnum\n=1 and~\fi % ‘and’ precedes the last value
\number\p \advance\n by -1 }
\def\printifprime{\testprimality \ifprime\printp\fi}
\def\testprimality{{\d=3 \global\primetrue
\loop\trialdivision \ifunknown\advance\d by2 \repeat}}
\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.

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

Answer 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.

edit regarding the "Renewed answer":

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

---

Initial answer.

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}

Answer 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

Answer 6

The Eratosthenes algorithm can be implemented in TeX with good visual output in log and in the terminal. The internal data can be printed each step using \message{"\eratdata"}.

\newcount\tmpnum
\def\eratA{\def\eratdata{}\def\eratE{\eratF}\tmpnum=1\eratB}
\def\eratB#1{%
   \ifx.#1\edef\eratdata{\eratdata{\the\tmpnum}}%
        \expandafter\eratE\expandafter\relax
   \else\ifx\relax#1\let\continue=\end \else
        \edef\eratdata{\eratdata\ifx x#1x\else{#1}\fi}%
        \advance\tmpnum by1
        \expandafter\def\expandafter\eratE\expandafter{\eratE\eratF}%
        \expandafter\expandafter\expandafter\eratB\fi\fi
}
\def\eratC#1{\ifx\relax#1\else
   \ifx x#1\else \edef\eratOUT{\eratOUT,#1}\fi
   \expandafter\eratC\fi
}
\def\eratF#1\relax#2{\ifx#2\relax \else
   \ifx\relax#1\relax\edef\eratdata{\eratdata x}\def\next{\eratE\relax}%
   \else\edef\eratdata{\eratdata#2}\def\next{#1\relax}%
   \fi \expandafter\next \fi
}
\def\erat#1{\let\continue=\relax
   \loop #1%
       \expandafter\eratA\eratdata\relax
       \ifx\continue\relax \repeat
   \def\eratOUT{\eratD}\def\eratD##1{}%
   \tmpnum=1
   \expandafter\eratC\eratdata\relax
}

\def\eratdata{x.........................................}
\erat{\message{"\eratdata"}}
\message{Prime numbers = \eratOUT}
\end

The result on the terminal looks like:

"x........................................."
"x{2}.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x"
"x{2}{3}x.x.xxx.x.xxx.x.xxx.x.xxx.x.xxx.x.xxx.x"
"x{2}{3}x{5}x.xxx.x.xxx.x.xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx.x.xxx.x.xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x.xxx.x.xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx.x.xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x.xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx.xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx{23}xxxxx.x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx{23}xxxxx{29}x.xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx{23}xxxxx{29}x{31}xxxxx.xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx{23}xxxxx{29}x{31}xxxxx{37}xxx.x"
"x{2}{3}x{5}x{7}xxx{11}x{13}xxx{17}x{19}xxx{23}xxxxx{29}x{31}xxxxx{37}xxx{41}x"
Prime numbers = 2,3,5,7,11,13,17,19,23,29,31,37,41