views:

777

answers:

4

The newspaper for the Computer Science-line at my school (called readme, is's norwegian, page 19) had a fun competition:

Write the shortest possible Java-code for this problem:

Take in an integer (as a string in the first entry of a string array, since the Java main method only takes a string array) as an argument, and write out first all numbers below this number that are primes, and then all numbers that are not primes. The shortest code wins!

As an answer, I will post the shortest Java-code that won the competition. I wonder if the Stack Overflow Community can make a code that is shorter If you know Norwegian, you will see that you could've won a bottle of champagne if you had done it, but unfortunately the last submit date of the competition is over.

How would you have solved this problem?

+2  A: 

The Java-code that won the competition (153 bytes without spacing, spacing included here for readability):

class F {
   public static void main(String[] a) {
      for (int i, j, k = 2; k-- > 0;)
         for (i = 1; i++ < new Long(a[0]);) {
            for (j = i; i % --j > 0;)
               ;
            if (k > 0 ? j < 2 : j > 1)
               System.out.println(i);
         }
      }
   }
Espenhh
did you leave in the spacing between public and static....
Milhous
Why int and not long?
Apocalisp
int is shorter than long
Brad Gilbert
This program does not terminate for inputs larger than Integer.MAX_VALUE.
Apocalisp
new Long(String) is rather expensive cf. Long.parseLong(String) for a loop, but it is shorter. ;)
Peter Lawrey
+5  A: 

I was already doing it in Haskell before you changed the title to "Java". Since this is a community wiki, here it is anyway.

primes n = 
let sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0] in 
let primes = takeWhile (<n) $ sieve [2..] in 
([0..n] \\ primes, primes)

*Main> primes 20
([0,1,4,6,8,9,10,12,14,15,16,18,20],[2,3,5,7,11,13,17,19])
Unknown
Nice. This could be shortened by using simple trial division, rather than a sieve of sorts (and the above algorithm has worse performance than trial division; see the Melissa O'Neill's paper about this).
Gracenotes
@ Gracenotes do you have a link to the paper?
Unknown
Accepted this answer, if somebody comes up with something shorter I will change the acceptance =)
Espenhh
I think Gracenotes is referring to this paper: [The Genuine Sieve of Eratosthenes][1] [1]: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
+3  A: 

Just for fun, here's a Java version of the previous Haskell answer. This program terminates for all arguments, given sufficient heap.

import fj.data.Natural;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
import fj.pre.Show;
import static fj.pre.Show.streamShow;
import static fj.pre.Show.naturalShow;
import static fj.data.Natural.ZERO;
import static fj.data.Natural.natural;
import fj.P1;
import fj.F;
import static fj.data.Enumerator.naturalEnumerator;

import java.math.BigInteger;

public class Primes2
  {public static Stream<Natural> sieve(final Stream<Natural> xs)
    {return cons(xs.head(), new P1<Stream<Natural>>()
      {public Stream<Natural> _1()
        {return sieve(xs.tail()._1().filter(new F<Natural, Boolean>()
          {public Boolean f(final Natural x)
            {return !naturalOrd.eq(x.mod(xs.head()), ZERO);}}));}});}

  public static Stream<Natural> primes(final Natural n)
    {return sieve(forever(naturalEnumerator, natural(2).some()))
            .takeWhile(naturalOrd.isLessThan(n));}

  public static void main(final String[] a)
    {final Natural n = natural(new BigInteger(a[0])).some();
     final Show<Stream<Natural>> s = streamShow(naturalShow);
     s.println(primes(n));
     s.println(range(naturalEnumerator, ZERO, n)
               .minus(naturalOrd.equal(), primes(n)));}
}

The fj package is from here.

Apocalisp
Wow, great work :)
Espenhh
A: 

My attempt in Ruby. 93 characters.

def s n
(a=(2..n).to_a).each{|n|a.reject!{|k|k%n==0&&k/n!=1}}
p[[1]+a,(2..n).to_a-a]
end
samuil