# All primes from 0 to 1000

Is it possible to make this C code smaller? It prints out all primes from 0 to 1000.

C, 89 chars

int i,p,c;for(i=2;i<1e3;i++){c=0;for(p=2;p<i;p++)if(i%p==0)c++;if(c==0)printf("%u\n",i);}

• Just to pre-empt some "We don't want language-specific challenges" downvotes, asking for help golfing down some code is on-topic and a different story than challenges. – Martin Ender Jan 9 '15 at 20:00
• Do we need to preserve the algorithm, or only the end result? – John Dvorak Jan 9 '15 at 20:03
• I'd start i at 2 to be strictly accurate, since this prints 0 and 1. – histocrat Jan 9 '15 at 20:23
• are you trying to make the code execute faster or trying to use less characters in the source code? – user3629249 Jan 9 '15 at 20:37
• Since you're asking for assistance with golf, it would be helpful to include the character count of your current solution in your post (I make it as 89). – Mark Reed Jan 9 '15 at 20:57

59 57 bytes

Based on @feersum solution but the primality check can be golfed further

for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);


• The bound check can be golfed a bit more: d=p++%999. Otherwise, this looks pretty airtight golfing job! – Runer112 Jan 12 '15 at 14:43

# 67 bytes

In C there's no real alternative to trial division, but it can certainly be golfed a bit.

for(int p=1,d;p++<999;d&&printf("%d\n",p))for(d=p;--d>1;)d=p%d?d:1;


Requires C99 initial declarations, which saves 1 byte.

(I wrote this not realizing the size limitations on integers in C, so it's likely not actually useful for shortening the code.)

First, a word about algorithm. Before golfing your code, you should think about the best overall strategy to get the result.

You're checking primality by doing trial division -- testing each potential divisor p of i. That's costly in characters because it takes two loops. So, testing primality without a loop is likely to save characters.

An often shorter approach is to use Wilson's Theorem: the number n is prime if and only if

fact(n-1)%n == n-1


where fact is the factorial function. Since you're testing all possible n from 1 to 1000, it's easy to avoid implementing factorial by keeping track of the running product P and updating it by P*=n after each loop. Here's a Python implementation of this strategy to print primes up to a million.

Alternatively, the fact that your program only has to be right up to 1000 opens up another strategy: the Fermat primality test. For some a, every prime n satisfies

pow(a,n-1)%n == 1


Unfortunately, some composites n also pass this test for some a. These are called Fermat pseudoprimes. But, a=2 and a=3 don't fail together until n=1105, so they suffice for your purpose of checking primes until 1000. (If 1000 were instead 100, you'd be able to use only a=2.) So, we check primality with (ungolfed code)

pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1


This also fails to recognize primes 2 and 3, so those would need to be special-cased.

Are these approaches shorter? I don't know because I don't code in C. But, they're ideas you should try before you settle on a piece of code to start eking out characters.

• Wilson's theorem is not useful in C because ints are 32-bit. Same goes for Fermat's. – feersum Jan 9 '15 at 20:58
• @feersum Oh, shoot. That's a problem for the factorials too. Is there a big-int type? – xnor Jan 9 '15 at 20:59
• @xnor Not built-in. – Martin Ender Jan 9 '15 at 21:10
• if one defines fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; } then the result won't overflow a 32 bit integer for even fairly large values of n. (m is the modulus) – apnorton Jan 9 '15 at 22:49
• @anorton I think you mean (n*fact(n-1,m)) % m. Which highlights the problem: you cannot avoid the recursion in the implementation of fact because m will be different for each iteration of the outer loop. – hvd Jan 10 '15 at 16:19

# 78 77 characters

(Just applied some tricks learned in other languages.)

int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}


## 76 characters in C99 mode

for(int i=0,p,c;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}


## 58 chars (or 61 for a complete program)

Another reuse of my answer to a similar question.
EDIT: stand-alone code piece, no function to call.

for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));


Complete program:

n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}


# 67 64 bytes

Inspired by Alchymist's solution :

int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}