css: set PRE’s max-width so it doesn’t stretch the viewport

[mina86.com.git] / posts / prime-numbers-less-than-a-hundred.en.html

<!-- subject: Prime numbers less than 100 -->
<!-- date: 2010-12-12 18:30:59 -->
<!-- tags: c, primes, brain-teaser -->
<!-- categories: Articles, Misc, Techblog -->

<p>Anyone working in a major company must have been hit by some
‘funny’ mail from a coworker that helps everyone gets through the
day.  No different at my office — at one point all
engineers have been challenged to write the shortest code in
C that prints all prime numbers (and only prime numbers) less
than a hundred each on separate line.

<p>This is an interesting brain-teaser so posting it here so others
may choose to think about it while <a
href="http://xkcd.com/303/">their code’s compiling</a>.

<p>Of course, a ‘C program’ needs not to be taken too seriously — depending on
not too far fetched undefined behaviours of given implementation is all right
(but please do not use <code>system</code> or <code>exec</code> family of calls;
not that I can see how that would help).

<p>By the way, if you’re interested in how this challenge looks solved in Rust,
  I’ve <a href="/2021/prime-numbers-less-than-a-hundred-in-rust/">described
  that</a> as well.

<!-- FULL -->

<h2>The solution</h2>

<p>I have managed to came up with two 61-character (this excludes new
line at the end of the file) solutions — one uses two loops
and the other only one:

<pre>main(i,j){for(;j=i++&lt;99;)for(;++j&lt;i||printf("%d\n",i),i%j;);}</pre>
<pre>
main(j,i){for(i=2;i%++j||(i>j||printf("%d\n",i),j=i++&lt;99););}</pre>

<p>I have used a comma operator to print the prime number
but <a href="#comm1573336">Wasacz solution</a> shown that it is not
necessary and thus a 60-character solution can be created:

<pre>main(i,j){for(;j=++i&lt;99;j&lt;i||printf("%d\n",i))for(;i%++j;);}</pre>

<h2>Analysis</h2>

<p>Let’s look at the code to see how much does it bend the
C language rules.  I will look through some of the surprising
constructs and try to clarify them.  Some of the comments are of
historic importance only but nonetheless may be interested for
a C programmer curious about ins and outs of the
language.

<p><b>Implicit return type</b>.  Starting from the beginning, the
<code>main</code> function has no return type specified.  That is
actually quite all right since C89 defaults function’s return type to
<code>int</code>.

<p><b>Old function prototype</b>.  This is not the only ‘problem’ with
the function though.  <code>main</code>’s prototype lacks also argument
types.  This is also a perfectly valid C syntax.  In original design
types were not part of function declaration and, not to break old code,
this (otherwise deprecated syntax) remained in C89.  The old function
definition looks as follows:

<pre>
<i>rettype</i> foo(<i>arg1</i>, <i>arg2</i>)
        <i>type1</i> <i>arg1</i>;
        <i>type2</i> <i>arg2</i>;
{
        …
}</pre>

<p>Programmers were responsible for guaranteeing correct function
invocation which lead to many hard to find bugs and thus
a <code>sparse</code> tool was created which, among other things,
checked whether all function invocations match function
definition.

<p>Digging more in this topic, when C89 standard was published not all
compilers were fully compatible with it (in particular, not all
supported the new function prototypes), which lead programmers to the
use of a macro that let them omit function prototype when compiling
with old compiler, ie.:

<pre>
#if __STDC__
#  define P(x) x
#else
#  define P(x) ()
#endif

<i>rettype</i> foo P((<i>type1</i>, <i>type2</i>));</pre>

<p>What is quite important to note here is that in C empty arguments
list in function declaration does not mean that the function take no
argument (which is true in C++).  It means function take unspecified
number of arguments.  To declare function with no arguments one needs
to use <code>void</code> keyword, ie.: <code>int foo(void)</code>.

<p><b>Implicit type</b>.  So, what <em>is</em> the type of
<code>main</code> arguments?  There was none specified anywhere.  This
is, yet again, quite all right since C89 defaults to <code>int</code>.
Generally, anything that has been declared but has no type specified is
of type <code>int</code>.  For example <code>static i;</code> is the
same thing as <code>static int i;</code>.

<p><b>Incorrect argument type</b>.  This brings us to the next issue.
The two <code>main</code> function prototypes defined by the standard
are:

<pre>
int main(int, char **);
int main(void);</pre>

<p>This stays in conflict with our second argument being (implicitly)
defined as having type <code>int</code>.  This is the first place were
undefined behaviour is introduced.  Theoretically, undefined behaviour
can lead to anything, including daemons coming out of your nose, but
because in most (for some definitions of ‘most’) implementations
<code>sizeof(int)</code> is no smaller than <code>sizeof(char *)</code>,
passing convention for the two type is compatible and <code>int</code> has
no trap representations, we are in the clear.

<p><b><code>i</code>’s initialisation</b>.  Looking carefully at the
code one notices that <code>i</code> is never initialised and instead it
uses the value passed as first argument to <code>main</code> as its
initial value.  This reveals a quite interesting bug: if one calls the
program with some arguments, it will skip initial prime numbers.

<p>What I find more fascinating though is situation where
<code>main</code>’s first argument is zero (which standard permits).  In
this situation <code>j</code> will overflow (which is undefined
behaviour for signed integers) and the second loop will finish
when <code>j</code> reaches <code>-1</code>.  This is also a situation
where <code>b/a</code> will yield undesired true value hence it is
better to use <code>j&lt;i</code> comparison.

<p><b>Implicit declaration</b>.  Obviously, to output the number we’ve
used <code>printf</code> function.  This is a straight-forward approach, yet we
are missing its declaration.  And yet again, this is quite all right from C89’s
point of view.  If function declaration is missing an implicit declaration based
on types of passed arguments with <code>int</code> as a return type is assumed.

<p>Let’s stay here for a second because this is a good
opportunity to yet again remind everybody not to cast result of
<code>malloc</code> function.  Consider the following code:

<pre>
int main(void) {
        int *p = (int *)malloc(sizeof *p); /* incorrect */
        return p ? 0 : *p;
}</pre>

<p>Some compilers will (rightly) accept such code with no complains
even though one forgot to include the <code>stdlib.h</code> header file.
Because of the implicit function declaration rule the compiler will
assume a <code>int malloc(size_t)</code> prototype and then (because
of cast operator) will obediently convert <code>int</code> into
a pointer to <code>int</code>.  Without the cast, compiler will have
to complain about implicit conversion from <code>int</code> to pointer
type reminding about the header file:

<pre>
int main(void) {
        int *p = malloc(sizeof *p); /* correct */
        return p ? 0 : *p;
}</pre>

<p><b>Lack of return</b>.  The last issue with the prime number
printing code is the lack of return statement.  C99 specifies that
‘reaching the <code>}</code> that terminates the <code>main</code> function
returns a value of zero.’  One cannot hide behind C99 though since the
code uses various C89 only ‘features’ (implicit type, implicit
function declaration, etc).  Yes, this is another undefined behaviour
in the code.

<p>Hope you have all enjoyed this little brain-teaser and maybe even
got some interesting information about the C language from this
entry.

<!-- COMMENT -->
<!-- date: 2010-12-12 21:50:52 -->
<!-- nick: mina86 -->
<!-- nick_url: http://mina86.com -->

<p>72 actually since "%d " needs to be "%d\n".

<p>Three hints:
<ol>
<li>Is <code>if</code> the only control structure that can be used?
<li>Would pre-incrementation (as opposed to post-incrementation) change anything?
<li>Do you need to compare with 100?
</ol>

<!-- COMMENT -->
<!-- date: 2010-12-13 10:16:10 -->
<!-- nick: Wasacz -->
<!-- nick_url: http://blog.wasacz.net -->

<p>Hints applied: https://ideone.com/iHe9v

<p>;)

<!-- COMMENT -->
<!-- date: 2010-12-13 11:19:00 -->
<!-- nick: mina86 -->
<!-- nick_url: http://mina86.com -->

<p>Yep, that’s it. :) When I get back from work I’ll also post a version with one loop as it may be interesting.

<!-- COMMENT -->
<!-- date: 2010-12-13 11:24:15 -->
<!-- nick: mina86 -->
<!-- nick_url: http://mina86.com -->

<p>Ha! Actually, modifying your code I got down to 60. ;) Hint: Does you need the literal <code>1</code> value in the source code?

<!-- COMMENT -->
<!-- date: 2010-12-13 11:54:38 -->
<!-- nick: Wasacz -->
<!-- nick_url: http://blog.wasacz.net -->

<p>Wow ;) https://ideone.com/LqjjH

<!-- COMMENT -->
<!-- date: 2010-12-14 08:42:44 -->
<!-- nick: rozie -->
<!-- nick_url: http://rozie.blox.pl/ -->

<p>Perlgolfa widziałem, ale Cgolf? 8-o<br />
Fajne. ;-)

<!-- COMMENT -->
<!-- date: 2010-12-29 22:40:30 -->
<!-- nick: mina86 -->
<!-- nick_url: http://mina86.com -->

<p>Still, you can optimise it a bit (85):

<pre>main(n,j){long long x=0x3986291891100;for(puts("2");x/=4;printf("%d\n",n+=x%4*2+2));}</pre>