Кратчайший код для простого расчета

Question

Газета для линии Computer Science в моей школе (называемая readme , на норвежском языке, стр. 19) провела веселый конкурс на написание кратчайшего Java-кода для следующей задачи.

Возьмите целое число (как строку в первой записи массива строк, поскольку основной метод Java принимает только массив строк) в качестве аргумента и запишите сначала все числа ниже этого числа, которые являются простыми числами, а затем все числа, которые не являются простыми числами. Самый короткий код выигрывает!

В качестве ответа я опубликую самый короткий Java-код, выигравший конкурс. Интересно, сможет ли Сообщество переполнения стека создать код, который будет короче? Если вы знаете норвежский язык, вы увидите, что могли бы выиграть бутылку шампанского, если бы сделали это, но, к сожалению, последняя дата подачи заявок на участие в конкурсе окончена.

Как бы вы решили эту проблему?

Answer 1

Я уже делал это в Haskell, прежде чем вы изменили название на "Java". Так как это вики сообщества, в любом случае здесь.

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:) Сокращение имен и удаление пробелов составляет 79 символов:

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)

здесь также меняется порядок полученной пары, и используется n-1 согласно спецификации.

Использование неоптимального пробного деления снижает его до 50 символов :

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

Answer 2

Java-код, победивший в конкурсе (153 байта без пробелов, здесь для удобства чтения включен интервал):

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

Просто для удовольствия, вот Java-версия предыдущего ответа на Haskell. Эта программа завершает работу для всех аргументов при достаточной куче.

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

Пакет fj отсюда.

Answer 4

Python, 65 символов

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

Использование:

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

Моя попытка в Ruby. 93 символа.

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 6

Для полноты, еще два определения Haskell. Архетип

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

и абсолютный чемпион по краткости

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

Answer 7

Простой и понятный код может выглядеть так:

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

если вам нужен код js: n - это максимум (62 символа)

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

Answer 9

133 символов: -)

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