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
(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.
Another reuse of my answer to a similar question.
EDIT: stand-alone code piece, no function to call.