• mina86.com

  • Categories
  • Code
  • Contact
  • Prime numbers less than 100

    Posted by Michał ‘mina86’ Nazarewicz on 12th of December 2010 | (cite)

    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.

    This is an interesting brain-teaser so posting it here so others may choose to think about it while their code’s compiling.

    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 system or exec family of calls; not that I can see how that would help).

    By the way, if you’re interested in how this challenge looks solved in Rust, I’ve described that as well.

    The solution

    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:

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

    I have used a comma operator to print the prime number but Wasacz solution shown that it is not necessary and thus a 60-character solution can be created:

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

    Analysis

    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.

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

    Old function prototype. This is not the only ‘problem’ with the function though. main’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:

    rettype foo(arg1, arg2)
    	type1 arg1;
    	type2 arg2;
    {
    	…
    }

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

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

    #if __STDC__
    #  define P(x) x
    #else
    #  define P(x) ()
    #endif
    
    rettype foo P((type1, type2));

    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 void keyword, ie.: int foo(void).

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

    Incorrect argument type. This brings us to the next issue. The two main function prototypes defined by the standard are:

    int main(int, char **);
    int main(void);

    This stays in conflict with our second argument being (implicitly) defined as having type int. 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 sizeof(int) is no smaller than sizeof(char *), passing convention for the two type is compatible and int has no trap representations, we are in the clear.

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

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

    Implicit declaration. Obviously, to output the number we’ve used printf 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 int as a return type is assumed.

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

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

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

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

    Lack of return. The last issue with the prime number printing code is the lack of return statement. C99 specifies that ‘reaching the } that terminates the main 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.

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