Shortest-code for prime-calculation

Question

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?

Answer 1

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);
         }
      }
   }

Answer 2

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])

Answer 3

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.

Answer 4

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