Codice più breve per il calcolo primo

Question

Il giornale per l'informatica nella mia scuola (chiamato readme , è norvegese, pagina 19) ha avuto una divertente competizione per scrivere il codice Java più corto possibile per il seguente problema.

  

Accetta un numero intero (come stringa nella prima voce di un array di stringhe, poiché il metodo principale Java accetta solo un array di stringhe) come argomento e scrivi prima tutti i numeri sotto questo numero che sono numeri primi, quindi tutti i numeri che non sono numeri primi. Vince il codice più corto!

Come risposta, posterò il codice Java più corto che ha vinto la competizione. Mi chiedo se la community di Stack Overflow può rendere un codice più breve Se conosci il norvegese, vedrai che avresti potuto vincere una bottiglia di champagne se l'avessi fatto, ma sfortunatamente l'ultima data di invio del concorso è scaduta.

Come avresti risolto questo problema?

Answer 1

Lo stavo già facendo in Haskell prima che tu cambiassi il titolo in "Java". Poiché questa è una wiki della comunità, eccola qui comunque.

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

(modifica :) Accorciare i nomi e rimuovere gli spazi bianchi rende 79 caratteri:

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)

qui viene anche scambiato l'ordine della coppia risultante e viene utilizzato n-1 , come da specifica.

L'uso della divisione di prova non ottimale lo porta a 50 caratteri :

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

Answer 2

Il codice Java che ha vinto la competizione (153 byte senza spaziatura, spaziatura inclusa qui per la leggibilità):

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

Solo per divertimento, ecco una versione Java di la precedente risposta Haskell . Questo programma termina per tutti gli argomenti, dato un mucchio sufficiente.

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

Il pacchetto fj è da qui.

Answer 4

Il mio tentativo in Ruby. 93 caratteri.

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 caratteri

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

Utilizzo:

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

se desideri un codice js: n è il massimo (62 caratteri)

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

Answer 7

Un codice facile da capire e intelligente può essere come:

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

Per completezza, altre due definizioni di Haskell. L'archetipo

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

e il campione assoluto in breve,

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

Answer 9

133 caratteri :-)

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