Code le plus court pour le calcul du nombre premier

Question

Le journal de la ligne d'informatique de mon école (appelé readme , c’est norvégien, page 19) a eu une compétition amusante pour écrire le code Java le plus court possible pour le problème suivant.

  

Prenez un entier (sous forme de chaîne dans la première entrée d'un tableau de chaînes, car la méthode principale Java ne prend qu'un tableau de chaînes) en tant qu'argument et écrivez d'abord tous les nombres premiers sous ce nombre qui sont des nombres premiers, puis tous les nombres qui ne sont pas des nombres premiers. Le code le plus court gagne!

En guise de réponse, je publierai le code Java le plus court ayant remporté le concours. Je me demande si la communauté Stack Overflow peut créer un code plus court. Si vous connaissez le norvégien, vous verrez que vous auriez pu gagner une bouteille de champagne si vous l'aviez fait. Malheureusement, la dernière date de soumission du concours est révolue.

Comment auriez-vous résolu ce problème?

Answer 1

Je le faisais déjà à Haskell avant que vous ne changiez le titre en "Java". Puisqu'il s'agit d'un wiki de communauté, le voici quand même.

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:) La réduction des noms et la suppression des espaces en font 79 caractères:

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)

ici aussi, l'ordre de la paire résultante est échangé et n-1 est utilisé, conformément à la spécification.

L'utilisation de la division d'essai sous-optimale réduit le nombre à 50 caractères :

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

Answer 2

Code Java ayant remporté le concours (153 octets sans espacement, espacement inclus pour des raisons de lisibilité):

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

Juste pour le plaisir, voici une version Java de la réponse précédente de Haskell . Ce programme se termine pour tous les arguments, avec suffisamment de tas.

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

Le package fj est à partir d'ici.

Answer 4

Ma tentative en Ruby. 93 caractères.

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 caractères

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

Utilisation:

>>> 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 vous souhaitez un code js: n est le maximum (62 caractères)

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

Answer 7

Un code facile à comprendre et intelligent peut ressembler à:

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

Pour être complet, deux autres définitions Haskell. L'archétype

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

et le champion absolu dans la brièveté,

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

Answer 9

133 caractères: -)

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