9
0
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);}
Jonas Grunau
Posted 2015-01-09T19:58:35.403
Reputation: 93
7
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
Alchymist
Posted 2015-01-09T19:58:35.403
Reputation: 544
2The bound check can be golfed a bit more: d=p++%999. Otherwise, this looks pretty airtight golfing job! – Runer112 – 2015-01-12T14:43:37.917
10
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.
feersum
Posted 2015-01-09T19:58:35.403
Reputation: 29 566
6
(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.
xnor
Posted 2015-01-09T19:58:35.403
Reputation: 115 687
1Wilson's theorem is not useful in C because ints are 32-bit. Same goes for Fermat's. – feersum – 2015-01-09T20:58:04.720
@feersum Oh, shoot. That's a problem for the factorials too. Is there a big-int type? – xnor – 2015-01-09T20:59:14.383
@xnor Not built-in. – Martin Ender – 2015-01-09T21:10:56.287
1if 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 – 2015-01-09T22:49:28.070
@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 – 2015-01-10T16:19:58.460
@hvd You're right that I meant n*fact(n-1, m)%m, but I don't see how that's a problem. We want m to be the same for each recursive step (which is what this program does); I'm not sure, but I think that a good compiler should optimize the recursion to an iterative solution, too. – apnorton – 2015-01-10T19:42:22.523
@anorton Yes, but then you've still got a nested loop. Here's a simple version with the recursion manually converted to a loop, so that it's easier to see: there's an outer loop in main, and an inner loop in fact. This answer suggests avoiding the inner loop by remembering fact(n - 1) from the previous iteration and just multiplying that by n, but that's no longer possible when you don't calculate fact(n - 1), when you only calculate fact(n - 1) % m.
4
(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);}
manatwork
Posted 2015-01-09T19:58:35.403
Reputation: 17 865
2
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++);}
ugoren
Posted 2015-01-09T19:58:35.403
Reputation: 16 527
1
Inspired by Alchymist's solution :
int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}
Sahil Arora
Posted 2015-01-09T19:58:35.403
Reputation: 341
6
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 – 2015-01-09T20:00:56.9304Do we need to preserve the algorithm, or only the end result? – John Dvorak – 2015-01-09T20:03:04.403
I'd start i at 2 to be strictly accurate, since this prints 0 and 1. – histocrat – 2015-01-09T20:23:59.187
are you trying to make the code execute faster or trying to use less characters in the source code? – user3629249 – 2015-01-09T20:37:10.227
1Since 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 – 2015-01-09T20:57:08.223
There is a better algorithm. Check Sieve of Eratosthenes. – user3286174 – 2015-01-12T23:29:14.113