Shortest-código para prime-cálculo

Question

O jornal para a Ciência-line computador na minha escola (chamado readme , é norueguês, página 19) tinha uma competição divertida para escrever o mais curto Java-código possível para o seguinte problema.

Leve em um inteiro (como uma string na primeira entrada de uma matriz de cadeia, uma vez que o método principal Java só tem uma matriz de cadeia) como um argumento, e escrever primeiros todos os números abaixo deste número que são primos, e, em seguida, todos os números que não são primos. As vitórias de código mais curto!

Como resposta, vou postar o mais curto Java-código que ganhou a competição. Pergunto-me se o estouro Comunidade Stack pode fazer um código que é mais curto Se você sabe norueguês, você vai ver que você poderia ter ganhado uma garrafa de champanhe se você tivesse feito isso, mas, infelizmente, a última data de submeter da competição é longo.

Como você teria resolvido este problema?

Answer 1

Eu já estava fazendo isso em Haskell antes que você mudou o título para "Java". Como este é um wiki comunidade, aqui é assim mesmo.

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:) Encurtar nomes e removendo espaço em branco torna 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)

aqui também a ordem do par resultante é trocado, e n-1 é usado, de acordo com a especificação.

Usando sub-óptima divisão julgamento traz à 50 caracteres :

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

Answer 2

O Java-código que venceu a competição (153 bytes sem espaçamento, espaçamento incluído aqui para facilitar a leitura):

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

Apenas por diversão, aqui está uma versão Java a resposta anterior Haskell . Este programa termina para todos os argumentos, dado pilha 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)));}
}

O pacote fj é daqui.

Answer 4

Minha tentativa em 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

Se você gostaria de um código js: n é o 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

Um fácil de entender e código inteligente pode ser como:

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, mais duas definições Haskell. O arquétipo

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

e o campeão absoluto na brevidade,

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