프라임 징계의 가장 짧은 코드

StackOverflow https://stackoverflow.com/questions/838004

  •  10-07-2019
  •  | 
  •  

문제

우리 학교에서 컴퓨터 과학 라인을위한 신문 ( readme, 노르웨이 인, 19 페이지)는 다음과 같은 문제에 대해 가능한 가장 짧은 Java 코드를 작성하기 위해 재미있는 경쟁을 가졌습니다.

정수 (Java 기본 메소드는 문자열 배열 만 사용하므로 문자열 배열의 첫 번째 항목에서 문자열로 사용)를 인수로 가져 가서이 숫자 아래의 모든 숫자를 먼저 기록한 다음 모든 숫자를 기록하십시오. 프라임이 아닙니다. 가장 짧은 코드가 승리합니다!

답으로, 나는 경쟁에서 승리 한 가장 짧은 Java 코드를 게시 할 것입니다. 스택 오버플로 커뮤니티가 노르웨이 인을 알고 있다면 더 짧은 코드를 만들 수 있는지 궁금합니다. 샴페인 한 병을 얻었을 수 있음을 알 수 있지만 불행히도 경쟁의 마지막 제출 날짜는 끝났습니다.

이 문제를 어떻게 해결했을까요?

도움이 되었습니까?

해결책

제목을 "Java"로 변경하기 전에 이미 Haskell에서하고있었습니다. 이것은 커뮤니티 위키이기 때문에 여기에 있습니다.

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

(편집하다:) 이름을 단축하고 공백을 제거하면 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]

다른 팁

경쟁에서 우승 한 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);
         }
      }
   }

재미를 위해, 여기에 자바 버전이 있습니다. 이전 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 패키지는 여기에서 왔습니다.

루비에서의 나의 시도. 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

파이썬, 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]
>>>

JS 코드를 원한다면 : N은 최대 (62 chars)

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

이해하기 쉽고 스마트 코드는 다음과 같습니다.

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

완전성을 위해 두 개의 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)

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);
        }
    }
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top