7
\$\begingroup\$

Write a plain TeX program that lists the first two hundred primes (in base-10 notation). Including external files/resources is not permitted. The output may be to the terminal, the log file, or the actual dvi/pdf file, at your option, but should be easily readable to a human; in particular, there must be some delimiter (comma, space, newline,...) between consecutive primes. e-TeX and pdfTeX primitives are permitted. See this answer for a starting place.

Hard-coding the result is permitted, although I do not expect such an answer to win.

The answer with the lowest byte count wins.

\$\endgroup\$
  • \$\begingroup\$ What prevents us from just hard-coding the results? It might even be shorter than some code to generate them. \$\endgroup\$ – John Dvorak Mar 11 '14 at 15:59
  • 1
    \$\begingroup\$ @Jan Dvorak I guess this post prevents that. \$\endgroup\$ – ace_HongKongIndependence Mar 11 '14 at 16:02
  • 1
    \$\begingroup\$ If this wasn't just using TeX, it would be a duplicate. It is also generally frowned on to limit languages. \$\endgroup\$ – Hosch250 Mar 11 '14 at 16:19
  • \$\begingroup\$ @hosch250: That's why I tagged this code-challenge rather than code-golf. \$\endgroup\$ – Charles Staats Mar 11 '14 at 16:23
  • 3
    \$\begingroup\$ "The answer with the lowest byte count wins." means code-golf. A code challenge is a competition for creative ways to solve a programming puzzle with an objective winning criterion not covered by other scoring tags (e.g. code-golf). codegolf.stackexchange.com/tags/code-challenge/info \$\endgroup\$ – ace_HongKongIndependence Mar 11 '14 at 17:03
11
\$\begingroup\$

176 bytes (plain TeX without e-TeX or pdfTeX)

\let\n\newcount\n~\n\j\n\k2~3\loop\ifnum~<1224{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\advance\j2\repeat\ifx\x., \the~\fi}\advance~2\repeat\end

Algorithm

The algorithm is quite simple. It outputs the first prime number 2 and goes from the next prime number 3 to the 200th prime number 1223. Each number i is tested, if the odd number is divisible by 3 up to i-1 without even numbers (thanks Howard for the removal of the even numbers).

There is much room for optimizations of the run-time, e.g.:

  • The inner loop can be aborted, when the first divisor is found, see the comments.
  • The divisions only need to be done up to sqrt(i).

The result is a paragraph with comma separated numbers:

Result

Ungolfed version

% assign some count registers with short names
\newcount\i
\newcount\j
\newcount\k
% Output first prime number 2
2%
% Start loop with second prime number 3
\i=3 %
\loop
\ifnum\i<1224 % 1223 is 200th prime number
  {% group with curly braces because of the nested \loop
    \let\x=. % \x is changed, if \i is not prime
    % Test for all 2 <= j < i: trunc(i/j)*j == i
    % If true, then j is divisor of i and i is not prime
    \j=3
    \loop
    \ifnum\j<\i
      \k=\i
      \divide\k by \j
      \multiply\k by \j
      \ifnum\k=\i
        \let\x=! % \i is not prime
        % Optimization to break the loop:
        %   \let\iterate\empty
        % Then also \x can be removed: If the loop is not aborted,
        % then \iterate will have the meaning \relax and the
        % test "\ifx\x." can be replaced by "\ifx\iterate\relax".
      \fi
      \advance\j by 2
    \repeat
    \ifx\x.
      , \the\i % output prime number
    \fi
  }%
  \advance\i by 2 % test next odd number
\repeat
\end % end of job

Variant: Output in protocol file, 195 bytes

\let\n\newcount\n~\n\j\n\k~2\def\w{\wlog{\the~}}\w~3\loop\ifnum~<1224{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\advance\j2\repeat\ifx\x.\w\fi}\advance~2\repeat\end

The result is written to the .log file:

This is TeX, Version 3.1415926 (TeX Live 2013) (format=tex 2013.5.21)  11 MAR 2014 18:33
**test
(./test.tex
~=\count26
\j=\count27
\k=\count28
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
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997
1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
1063
1069
1087
1091
1093
1097
1103
1109
1117
1123
1129
1151
1153
1163
1171
1181
1187
1193
1201
1213
1217
1223
 )
No pages of output.

Variant: Counting prime numbers, 197 bytes

The following variant also counts the prime numbers to get rid of the "hard-coded" 200th prime number. (I have added this variant at the end, because the question would also allow to hard-code all prime numbers.)

\let\a\advance\let\n\newcount\n\p\n~\n\j\n\k2\p1~3\loop\ifnum\p<200{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\a\j2\repeat\ifx\x., \the~\global\a\p1\fi}\a~2\repeat\end
\$\endgroup\$
  • \$\begingroup\$ Most basic improvement (without cost): also step the j loop by 2 instead of one. \$\endgroup\$ – Howard Mar 11 '14 at 18:18
  • 2
    \$\begingroup\$ @devnull: The question explicitly allows the hard-coding of all prime numbers, thus it is not cheating. However, I have also added a variant that counts prime numbers. \$\endgroup\$ – Heiko Oberdiek Mar 11 '14 at 18:48
  • \$\begingroup\$ @Howard: Thanks, answer updated. \$\endgroup\$ – Heiko Oberdiek Mar 11 '14 at 18:49
  • \$\begingroup\$ Oh, jeez! I didn't realize that you're the hyperref guy (besides much more contribution to CTAN). Thanks for all the great work. (Besides it's not hard to imagine that there cannot be better answer to this thread :-) ) \$\endgroup\$ – devnull Mar 12 '14 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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