Is it possible to make this C code smaller? It prints out all primes from 0 to 1000.
C, 89 chars
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 community
59 57 bytes
Based on @feersum solution but the primality check can be golfed further
Edited based on Runer112's comments
In C there's no real alternative to trial division, but it can certainly be golfed a bit.
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
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
fact is the factorial function. Since you're testing all possible
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
pow(a,n-1)%n == 1
Unfortunately, some composites
n also pass this test for some
a. These are called Fermat pseudoprimes. But,
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.
(Just applied some tricks learned in other languages.)
Another reuse of my answer to a similar question.
EDIT: stand-alone code piece, no function to call.
Inspired by Alchymist's solution :