Código más corto para cálculo de prima

Question

El periódico de la línea Computer Science en mi escuela (llamado readme , es noruego, página 19) tuvo un concurso divertido para escribir el código Java más corto posible para el siguiente problema.

  

Tome un número entero (como una cadena en la primera entrada de una matriz de cadenas, ya que el método principal de Java solo toma una matriz de cadenas) como argumento, y escriba primero todos los números debajo de este número que son números primos, y luego todos los números que no son primos. ¡El código más corto gana!

Como respuesta, publicaré el código Java más corto que ganó la competencia. Me pregunto si la Comunidad Stack Overflow puede hacer un código más corto. Si conoces noruego, verás que podrías haber ganado una botella de champán si lo hubieras hecho, pero desafortunadamente la última fecha de envío de la competencia ha terminado.

¿Cómo habría resuelto este problema?

Answer 1

Ya lo estaba haciendo en Haskell antes de que cambiaras el título a "Java". Como se trata de una wiki comunitaria, aquí está de todos modos.

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

(editar :) Acortar nombres y eliminar espacios en blanco hace 79 caracteres:

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)

aquí también se intercambia el orden del par resultante, y se usa n-1 , según la especificación.

El uso de una división de prueba subóptima lo reduce a 50 caracteres :

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

Answer 2

El código Java que ganó la competencia (153 bytes sin espacio, espacio incluido aquí para facilitar la lectura):

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 por diversión, aquí hay una versión Java de la respuesta anterior de Haskell . Este programa finaliza para todos los argumentos, dado un montón suficiente.

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

El paquete fj es de aquí.

Answer 4

Mi intento en Ruby. 93 caracteres.

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 caracteres

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

Uso:

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

si desea un código js: n es el máximo (62 caracteres)

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

Answer 7

Un código fácil de entender e inteligente puede ser:

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

Para completar, dos definiciones más de Haskell. El arquetipo

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

y el campeón absoluto en brevedad,

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

Answer 9

133 caracteres :-)

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