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);}
Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this communityIs 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);}
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.
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
d=p++%999
. Otherwise, this looks pretty airtight golfing job!
\$\endgroup\$
(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.
int
s are 32-bit. Same goes for Fermat's.
\$\endgroup\$
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\$
(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\$
(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);}
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);}
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++);}
Inspired by Alchymist's solution :
int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}