mina86.com

Prime numbers less than 100

Get back to “Jump to”

Anyone working in a big corporation 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 ;) ).

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 very 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 print the prime number we have used the printf(). This is a straight forward approach, but what is interesting is that there is no printf() declaration. And yet another time, 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). So 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.

Comments Atom feed with comments

Get back to “Jump to”

»»mina86

  • Added at2010/12/12, 21:50

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

Three hints:
1. Is “if” the only control structure that can be used?
2. Would pre-incrementation (as opposed to post-incrementation) change anything?
3. Do you need to compare with 100?

»»Wasacz

  • Added at2010/12/13, 10:16

Hints applied: http://ideone.com/iHe9v

;)

»»mina86

  • Added at2010/12/13, 11:19

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

»»mina86

  • Added at2010/12/13, 11:24

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

»»Wasacz

  • Added at2010/12/13, 11:54

Wow ;) http://ideone.com/LqjjH

»»rozie

  • Added at2010/12/14, 08:42

Perlgolfa widziałem, ale Cgolf? 8-o
Fajne. ;-)

»»mina86

  • Added at2010/12/29, 22:40

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

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

»»claiming back ppi

  • Added at2012/07/27, 22:15

I would like to thank you for the efforts you have put in penning this website.
I'm hoping to check out the same high-grade blog posts by you later on as well. In truth, your creative writing abilities has inspired me to get my own, personal site now ;) ppi claims

Add a comment

  • Single Return produces a line break.
  • More then that creates a paragraph.
  • Text preceded by four spaces means a block of code.
  • *emphasis*, _emphasis_,
  • **strong emphasis**, __strong emphasis__,
  • `inline code`, ``code ` more inline code``,
  • [Link](http://example.com/),
  • [Link](http://example.com/ "Title") and
  • <http://example.com/>.

End of the page, get back to “Jump to”.