10
\$\begingroup\$

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);}
Improve this question
\$\endgroup\$
6
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – Martin Ender
    Jan 9, 2015 at 20:00
  • 4
    \$\begingroup\$ Do we need to preserve the algorithm, or only the end result? \$\endgroup\$
    – John Dvorak
    Jan 9, 2015 at 20:03
  • \$\begingroup\$ I'd start i at 2 to be strictly accurate, since this prints 0 and 1. \$\endgroup\$
    – histocrat
    Jan 9, 2015 at 20:23
  • \$\begingroup\$ are you trying to make the code execute faster or trying to use less characters in the source code? \$\endgroup\$
    – user3629249
    Jan 9, 2015 at 20:37
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Mark Reed
    Jan 9, 2015 at 20:57

6 Answers 6

Reset to default
10
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

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--;);

Edited based on Runer112's comments

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ The bound check can be golfed a bit more: d=p++%999. Otherwise, this looks pretty airtight golfing job! \$\endgroup\$
    – Runer112
    Jan 12, 2015 at 14:43
6
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Wilson's theorem is not useful in C because ints are 32-bit. Same goes for Fermat's. \$\endgroup\$
    – feersum
    Jan 9, 2015 at 20:58
  • \$\begingroup\$ @feersum Oh, shoot. That's a problem for the factorials too. Is there a big-int type? \$\endgroup\$
    – xnor
    Jan 9, 2015 at 20:59
  • \$\begingroup\$ @xnor Not built-in. \$\endgroup\$
    – Martin Ender
    Jan 9, 2015 at 21:10
  • 1
    \$\begingroup\$ 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) \$\endgroup\$
    – apnorton
    Jan 9, 2015 at 22:49
  • \$\begingroup\$ @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. \$\endgroup\$
    – hvd
    Jan 10, 2015 at 16:19
4
\$\begingroup\$

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);}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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++);}
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

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);}
Improve this answer
\$\endgroup\$

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.