Kürzeste-Code für die Prime-Berechnung

Question

Die Zeitung für die Informatik-line an meiner Schule (so genannte readme , es ist norwegisch, Seite 19) einen Spaß Wettbewerb hatte die kürzest mögliche Java-Code für das folgende Problem.

schreiben

  

Nehmen in einer ganzen Zahl (als Zeichenkette in der ersten Eingabe eines String-Array, da die Java Haupt Methode nur einen String-Array nimmt) als Argument und auszuschreiben zunächst alle Zahlen unterhalb dieser Zahl, die Primzahlen sind, und dann Alle Zahlen, die keine Primzahlen sind. Der kürzeste Code gewinnt!

Als Antwort werde ich den kürzesten Java-Code schreiben, der den Wettbewerb gewonnen. Ich frage mich, ob der Stack-Überlauf Gemeinschaft kann einen Code machen, die kürzer ist, wenn Sie Norweger kennen, werden Sie sehen, dass Sie eine Flasche Champagner haben könnte gewonnen, wenn Sie es getan hatte, aber leider ist der letzte Tag des Wettbewerbs einreichen vorbei ist.

Wie würden Sie dieses Problem gelöst haben?

Answer 1

tat ich es schon in Haskell, bevor Sie den Titel „Java“ geändert. Da dies ein Community Wiki ist, hier ist es trotzdem.

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

(edit:) Kürzen Namen und Entfernen von Leerzeichen macht es 79 Zeichen:

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

Auch hier sind das resultierende Paar Auftrag wird ausgelagert, und n-1 verwendet wird, gemäß der Spezifikation.

Mit suboptimaler Probedivision bringt es auf 50 Zeichen :

p n=partition(\k->all((>0).rem k)[2..k-1])[2..n-1]

Answer 2

Der Java-Code, der den Wettbewerb gewonnen (153 Bytes ohne Abstand, Abstand eingeschlossen hier zur besseren Lesbarkeit):

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 3

Just for fun, hier ist eine Java-Version von die vorherige Antwort Haskell . Dieses Programm für alle Argumente beendet, ausreichend Haufen gegeben.

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

Das fj Paket ist von hier.

Answer 4

Mein Versuch in Ruby. 93 Zeichen.

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

Answer 5

Python, 65 Zeichen

print[i for i in range(2,input())if all(i%j for j in range(2,i))]

Verbrauch:

>>> print[i for i in range(2,input())if all(i%j for j in range(2,i))]
70
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
>>> 

Answer 6

Wenn Sie eine js Code wie: n sind der max (62 Zeichen)

  for(i=1; i<n;i++)
    {
        for(f = j= 2;j<i && f;)
            f = i%j++
        if(f) console.log(i)
    }

Answer 7

Ein leicht zu verstehen, und Smart-Code kann wie:

public class test3 {
    public static void main(String[] args) {
        for (int i = 2; i <= 100; i++) {
            int count = 0;
            for (int j = i / 2; j >= 2; j--) {
                if (i % j == 0)
                    count = count + 1;
            }
            if (count == 0)
                System.out.println(i);
        }
    }
}

Answer 8

Für die Vollständigkeit, zwei weitere Haskell Definitionen. Die archetypische

primes = map head . scanl (\\) [2..] . map (\p -> [p, p+p..]) $ primes
         where
         (\\) = Data.List.Ordered.minus

und die absolute Champion in Kürze

nubBy (((>1).).gcd) [2..]           -- (((>1).).gcd) meaning (\a b -> gcd a b > 1)

Answer 9

133 Zeichen: -)

class F {

    public static void main(String[] z) {

        l:
        for (int a=1,b; a < z; a += 2) {

            for (b = 2; b < a; b++)
                if (a % b == 0) 
                    continue l;
            System.out.println(a);
        }
    }
}