TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
2  
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
3  
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
2  
@kevin is LuaLaTeX allowed? – Loop Space Sep 20 '13 at 18:26

enter image description here

\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}
share|improve this answer
3  
you really shouldn't end with a hanging comma. (just being a pest.) – barbara beeton Sep 20 '13 at 20:43
1  
@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
3  
@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
\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

enter image description here

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.

share|improve this answer
2  
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} 

enter image description here

share|improve this answer
    
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

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.

Prime numbers in a circular chart

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|improve this answer

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 :

Blockquote

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.

prime tables

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

prime list

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}
share|improve this answer
    
Expandable implementation! Wow! – Aditya Apr 4 at 23:08
    
The series of \if1\xinttheiiexpr isCompositeWitness(2, #1, L)\relax\xintdothis0\fi etc.. can be coded with syntax isCompositeWitness(2, #1, L)?{0}{isCompositeWitness(3, #1, L)?{0}{isCompositeWitness(5, #1, L)?{0}{...{1}}}}}}} which also does lazy evaluation, but needs many closing braces. This would spare the overhead of extras \xinttheiiexpr but on other hand adds the overhead of something more complicated than \if test to check if non-zero. Fun to see variable substitution with L worked in the inserted expressions. And as I just tested, in fact the dothis/orthat way is faster. – jfbu Apr 5 at 19:21
    
Regarding the older part of the answer, from 2014, which is only for TeX integers, it actually fail on numbers close to 2^31 due to arithmetic overflows caused by the fact that e-TeX division rounds (arrrggggh) rather than truncates. In xint manual 6.17 A table of factorizations there is a macro \factorize_b where one can see the trick to avoid such arithmetic overflows: don't check if a=(a/b)*b but rather if a-b=(a/b-1)*b and oh that was clever not if a<b*b but if a-(b-1)*b<b... – jfbu Apr 5 at 19:41
    
What I say about use of "SuperComputers" appears obsolete as paper Jiang, Yupeng; Deng, Yingpu (2012). "Strong pseudoprimes to the first 9 prime bases". arXiv:1207.0063v1 explains having used only a PC. The conclusion is that 3825 12305 65464 13051 is the smallest composite number which is a strong pseudo prime for bases 2, 3, 5, 7, 11, 13, 17, 19 and 23. See also en.wikipedia.org/wiki/… – jfbu Apr 5 at 21:54
    
Relevant to TeX numbers: if n < 4,759,123,141, it is enough to test a = 2, 7, and 61. From Jaeschke "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926. See en.wikipedia.org/wiki/… and primes.utm.edu/prove/prove2_3.html – jfbu Apr 5 at 22:06

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.